LRC_1A - Xu hướng chung

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Authors:
Problem type

Bạn đang có ~N~ sản phẩm mỳ với giá trị từ ~1~ đến ~N~. Xu hướng chung của thị trường hiện nay là x và y, hãy tính số lượng các sản phầm mỳ trong ~N~ sản phẩm mà giá trị của nó chia hết cho ~x~ và ~y~.

Dữ liệu

Gồm 1 dòng chứa lần lượt các số nguyên ~n, x, y~ ~\le~ ~10^{12}~

Kết quả

In ra đáp án cần tìm

Test ví dụ

Dữ liệu

20 2 3

Kết quả

3

Test ví dụ 2

Dữ liệu

1000000000000 1 1

Kết quả

1000000000000

Giải thích : các số chia hết cho 2 và 3 là 6, 12, 18.


Comments

Please read the guidelines before commenting.



  • 1
    dinhvantung0611  commented on Jan. 13, 2024, 2:16 p.m.

    Ý tưởng: ~Hi mng, cố gắng hết sức rồi mới tham khảo cách giải nhé

    Bây giờ ta xét yêu cầu đề bài đó là tìm các số nằm trong khoảng [1, n] mà chia hết cho x và y. Vậy ta sẽ nghĩ ngay đến đi tìm bội chúng nhỏ nhất của 2 số, sau đó thì nhân lần lượt với 1, 2, 3, ... kiểm tra xem số đó có nằm trong đoạn từ [1, n] hay không (tuy nhiên chú ý nếu x = y = 1 thì in ra n luôn nhé). Hoặc đơn giản hơn thì ta sẽ lấy n // BCNN(x, y) (// phép chia thực) sẽ ra kết quả.

    Tuy nhiên do bộ test lên đến x = y = 10^12 cho nên nếu áp dụng CT tính BCNN = (x * y) / ƯCLN(x, y) sẽ làm tràn số (x * y = 10^12 * 10^12) (C++ thôi chứ python vẫn AC bình thường). Vậy ta cần tách phép chia này ra thành

    BCNN = (x / sqrt(ƯCLN(x, y))) * (y / sqrt(ƯCLN(x, y))) (tách mẫu thành căn rồi chia trước, sau đó mới nhân lại). Sẽ AC (chú ý để long long nhé).

    Mình thấy cách làm của nhiều bạn không hề sai, tuy nhiên hãy để ý cả các điều kiện về số mà bài cho nhé. Sẽ có bài cần để ý chi tiết này để AC bài.

    CƯỜNG GIẢ HỌ ĐINH. VẠN CỔ TỐI CƯỜNG


  • 0
    Doan_Linh_1303  commented on Dec. 9, 2023, 1:32 a.m.

    AI xem hộ mình code thiếu testcase nào với ạ

    include<bits/stdc++.h>

    using namespace std;

    long long countProductsDivisibleByXY(long long N, long long x, long long y) { if (x == 0 || y == 0) { return 0; } if(x==1 || y==1){ return N; } long long gcd = __gcd(x, y); long long lcm = (x * y) / gcd; long long count = N / lcm; return count; }

    int main() { long long N, x, y; cin >> N >> x >> y;

    long long result = countProductsDivisibleByXY(N, x, y);
    cout << result << endl;
    return 0;
    

    }


  • -11
    _SUGAR__DADDY_  commented on Dec. 2, 2023, 7:19 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 0
      Doan_Linh_1303  commented on Dec. 9, 2023, 1:33 a.m.

      còn trường hợp nào k bạn nhỉ mình chạy ko full