Hướng dẫn giải của Tin 10 Bài 7: Đếm ước
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
Cần đếm số ước nguyên dương của N, với N < 2·10^9.
Sub 1: Thử mọi số từ 1 đến N — ~O(N)~
Với mỗi d từ 1 đến N, nếu N chia hết cho d thì đếm thêm 1. Đúng nhưng N lên tới gần 2·10^9 nên quá chậm.
Kết quả chấm: đạt 14/20 test, 6 test quá thời gian, không sai test nào.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n;
cin >> n;
// Vét cạn: thử mọi số d từ 1 đến N, d là ước nếu N chia hết cho d
long long dem = 0;
for (long long d = 1; d <= n; d++)
if (n % d == 0) dem++;
cout << dem << "\n";
return 0;
}
Sub 2: Chỉ thử đến căn bậc hai của N — ~O(\sqrt{N})~
Ước của N đi thành từng cặp (d, N/d), trong đó luôn có một số không vượt quá √N. Vì vậy chỉ cần thử d từ 1 đến √N (tối đa khoảng 44721 vòng lặp). Mỗi d là ước thì đếm cả d và N/d, nhưng nếu d = N/d (N là số chính phương và d = √N) thì chỉ đếm một lần.
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;
cin >> n;
// Ước đi theo cặp (d, N/d) với d <= căn N, nên chỉ cần thử d đến căn N (khoảng 44721 với N < 2*10^9)
long long dem = 0;
for (long long d = 1; d * d <= n; d++) {
if (n % d == 0) {
dem++; // ước d
if (d != n / d) dem++; // ước đối xứng n/d (không đếm trùng khi d = căn N)
}
}
cout << dem << "\n";
return 0;
}
Bình luận