Hướng dẫn giải của F13: Số bạn bè
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
Hai số a, b là bạn bè nếu tổng các ước thực sự (không tính chính nó) của a bằng b và của b bằng a. Với a, b <= 1.2*10^6.
Sub 1: Thử mọi j từ 1 đến x-1 — ~O(a + b)~
Tổng ước thực sự của x được tính bằng cách thử mọi j từ 1 đến x-1. Với giới hạn 1.2*10^6 cách này vẫn đủ nhanh. Kiểm tra s(a) = b và s(b) = a.
Kết quả chấm: đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
// Tong cac uoc thuc su cua x, tinh bang cach thu tung j tu 1 den x-1
long long tongUoc(long long x) {
long long s = 0;
for (long long j = 1; j < x; j++)
if (x % j == 0) s += j;
return s;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long a, b;
cin >> a >> b;
cout << ((tongUoc(a) == b && tongUoc(b) == a) ? "Yes" : "No") << endl;
return 0;
}
Sub 2: Thử đến căn bậc hai — ~O(sqrt(a) + sqrt(b))~
Các ước đi theo cặp (i, x/i) nên chỉ xét i đến sqrt(x), cộng cả i và x/i khi khác nhau. Trường hợp x = 1 có tổng bằng 0.
Kết quả chấm: đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
// Tong cac uoc thuc su cua x, chi can xet i <= sqrt(x)
long long tongUoc(long long x) {
if (x == 1) return 0;
long long s = 1; // 1 la uoc thuc su cua x (x > 1)
for (long long i = 2; i * i <= x; i++) {
if (x % i == 0) {
s += i;
if (i != x / i) s += x / i; // tranh cong hai lan khi x la so chinh phuong
}
}
return s;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long a, b;
cin >> a >> b;
cout << ((tongUoc(a) == b && tongUoc(b) == a) ? "Yes" : "No") << endl;
return 0;
}
Bình luận