Hướng dẫn giải của F10: Các bội chung
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Cho M, N (<= 10^5). Tìm tất cả các bội chung của M và N không vượt quá tích M*N.
Sub 1: Thử mọi x từ 1 đến M*N — ~O(M*N)~
Duyệt x từ 1 đến MN và in x nếu chia hết cho cả M và N. Đúng nhưng MN có thể đến 10^10 nên 10 test bị TLE.
Kết quả chấm: đạt 10/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n, m;
cin >> n >> m;
long long lim = n * m;
// Vet can: thu tung so x tu 1 den M*N, xet x co chia het cho ca M va N
for (long long x = 1; x <= lim; x++)
if (x % n == 0 && x % m == 0) cout << x << " ";
cout << endl;
return 0;
}
Sub 2: Dùng BCNN và các bội của BCNN — ~O(số bội chung)~
Mọi bội chung là bội của BCNN(M, N) = M / gcd(M, N) * N (tính theo thứ tự này để tránh tràn). Các bội chung không vượt quá MN là l, 2l, 3l, ... với l = BCNN. Số lượng bằng gcd(M, N). Dùng long long vì MN <= 10^10.
Kết quả chấm: đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n, m;
cin >> n >> m;
long long lim = n * m;
long long l = n / __gcd(n, m) * m; // BCNN(n, m)
// Cac boi chung la boi cua BCNN; chi can lay l, 2l, 3l... <= M*N
for (long long x = l; x <= lim; x += l)
cout << x << " ";
cout << endl;
return 0;
}
Bình luận