Hướng dẫn giải của LOOP21: Số phong phú
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
Số phong phú là số N mà tổng các ước thực sự (không kể N) lớn hơn N. N ≤ 2·10^9 nên tổng các ước có thể vượt int, cần dùng long long.
Sub 1: Vét cạn — ~O(N)~
Duyệt i từ 1 đến N − 1, cộng i nếu i chia hết N, rồi so sánh tổng với N. Đạ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;
cin >> n;
// Vét cạn: cộng tất cả các ước của N không kể chính nó
long long sum = 0;
for (long long i = 1; i < n; i++)
if (n % i == 0) sum += i;
cout << (n < sum ? 1 : 0) << "\n";
return 0;
}
Sub 2: Duyệt đến căn bậc hai — ~O(√N)~
Mỗi cặp ước (i, N/i) với i ≤ √N được cộng vào tổng; chỉ cộng các ước khác N, và không cộng hai lần khi i = N/i. Đạ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;
// Tổng ước thực sự của N: duyệt i đến căn(N), mỗi cặp ước (i, N/i) cộng vào tổng
// Tổng có thể vượt 2*10^9 nên dùng long long
long long sum = 0;
for (long long i = 1; i * i <= n; i++) {
if (n % i == 0) {
long long j = n / i;
if (i < n) sum += i; // i là ước thực sự (khác N)
if (j != i && j < n) sum += j; // j là ước thực sự, tránh cộng trùng khi j = i
}
}
cout << (n < sum ? 1 : 0) << "\n";
return 0;
}
Bình luận