LRC_1A - Xu hướng chung
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
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.
Bình luận
Ý 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
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;
}
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
còn trường hợp nào k bạn nhỉ mình chạy ko full