Hướng dẫn giải của LOOP23: 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
Liệt kê các bội chung của N và M (N, M ≤ 100) không vượt X (X ≤ 10^9). Mọi bội chung đều là bội của BCNN(N, M), nên chỉ cần liệt kê các bội của BCNN.
Sub 1: Vét cạn — ~O(X)~
Thử từng số k từ 1 đến X, in k nếu chia hết cả N và M. Đạt 14/20 test (6 test còn lại quá giờ).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n, m, x;
cin >> n >> m >> x;
// Vét cạn: thử từng số k từ 1 đến X, in k nếu chia hết cả N và M
bool first = true;
for (long long k = 1; k <= x; k++) {
if (k % n == 0 && k % m == 0) {
if (!first) cout << " ";
cout << k;
first = false;
}
}
if (first) cout << 0;
cout << "\n";
return 0;
}
Sub 2: Liệt kê bội của BCNN — ~O(X / BCNN)~
BCNN(N, M) = N / ƯCLN(N, M) · M (tính trước khi nhân để tránh tràn). Bắt đầu từ BCNN và cộng dần BCNN cho đến khi vượt X. Nếu không có bội nào thì in 0. Đạ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, x;
cin >> n >> m >> x;
// Bội chung của N và M là bội của BCNN(N, M) = N*M / USCLN(N, M)
long long l = n / __gcd(n, m) * m;
bool first = true;
// Chỉ cần liệt kê các bội của BCNN không vượt X
for (long long k = l; k <= x; k += l) {
if (!first) cout << " ";
cout << k;
first = false;
}
if (first) cout << 0;
cout << "\n";
return 0;
}
Bình luận