Hướng dẫn giải của [200 đề thầy Đức] Bài 57: 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
Kiểm tra ~N~ có phải số phong phú hay không, tức là tổng các ước thực sự của ~N~ lớn hơn ~N~.
Sub 1: Duyệt mọi ước — ~O(N)~, dùng khi ~N \le 10^6~
Duyệt ~i~ từ 1 đến ~N-1~, cộng ~i~ nếu ~N \bmod i = 0~, rồi so sánh tổng với ~N~.
Nếu chỉ nộp sub này: đúng 15/19 test.
Sub 2: Duyệt đến căn bậc hai — ~O(\sqrt{N})~, dùng khi mọi trường hợp còn lại
Mỗi ước ~i \le \sqrt{N}~ kéo theo ước đối ~N/i~. Cộng cả hai, lưu ý không cộng trùng khi ~i = N/i~ và không cộng ~N~ chính nó. Tổng có thể vượt ~2 \cdot 10^9~ nên dùng số nguyên 64 bit.
Nếu chỉ nộp sub này: đúng 19/19 test.
Chương trình hoàn chỉnh
Chương trình đọc ~N~. Nếu ~N \le 10^6~ thì gọi sub1, ngược lại gọi sub2. Ví dụ: ~N=12~ có tổng ước thực sự là 16 > 12 nên là số phong phú; ~N=28~ có tổng bằng 28 nên không phải.
#include <bits/stdc++.h>
using namespace std;
long long N;
// Sub 1: vet can. Cong tat ca uoc thuc su cua N (i = 1..N-1). O(N), dung khi N <= 10^6.
void sub1() {
long long s = 0;
for (long long i = 1; i < N; i++)
if (N % i == 0) s += i;
cout << (N < s ? 1 : 0) << "\n";
}
// Sub 2: duyet i den can(N); moi uoc i co cap uoc doi N/i. O(sqrt(N)).
void sub2() {
long long s = 0;
for (long long i = 1; i * i <= N; i++) {
if (N % i == 0) {
long long j = N / i;
if (i < N) s += i; // i la uoc thuc su
if (j != i && j < N) s += j; // j la uoc thuc su khac i
}
}
cout << (N < s ? 1 : 0) << "\n";
}
int main() {
cin >> N;
if (N <= 1000000) sub1();
else sub2();
return 0;
}
Bình luận