Hướng dẫn giải của TIN10_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
Cho ba số N, M, X (N, M ≤ 100, X ≤ 10^9). Liệt kê các bội chung của N và M không vượt quá X; nếu không có thì in 0.
Sub 1: Vét cạn — ~O(X)~
Thử lần lượt mọi số k từ 1 đến X, k là bội chung nếu chia hết cho cả N và M. Đúng nhưng chậm khi X lớn: đạt 15/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;
// Vét cạn: thử mọi số k từ 1 đến X, k là bội chung 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: Bội của BCNN — ~O(X / BCNN(N, M))~
Mọi bội chung của N và M đều là bội của L = BCNN(N, M) = N·M / ƯCLN(N, M). Vì vậy chỉ cần in L, 2L, 3L, ... không vượt quá X. Chú ý tính N / ƯCLN(N, M) * M để tránh tràn số, và in 0 khi không có bội nào. Đạ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)
long long l = n / __gcd(n, m) * m;
// Liệt kê l, 2l, 3l, ... không vượt quá X
bool first = true;
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