Hướng dẫn giải của [Beginner Free Contest 06] SAMEPAIR
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ố có cùng tập ước nguyên tố khi và chỉ khi chúng có cùng ~rad(x)~, là tích các ước nguyên tố khác nhau của ~x~. Đếm cặp bằng cách nhóm các số theo ~rad~.
Sub 1: Vét cạn trên đoạn ngắn — ~O((R-L)^2)~, dùng khi ~R - L \le 1000~
Tính ~rad~ của từng số bằng chia thử, rồi thử mọi cặp để đếm cặp có cùng ~rad~. Nếu chỉ nộp sub này: đúng 60/100 test.
Sub 2: Sàng ~rad~ và đếm nhóm — ~O(R \log \log R)~
Sàng ~rad[x]~ cho mọi ~x \le R~: với mỗi số nguyên tố ~p~, nhân ~p~ vào ~rad~ của các bội của ~p~. Sau đó đếm số lần xuất hiện của mỗi ~rad~ trong đoạn; nhóm có ~c~ số cho ~c(c-1)/2~ cặp. Nếu chỉ nộp sub này: đúng 100/100 test.
Chương trình hoàn chỉnh
~main~ đọc ~L, R~, nếu ~R - L \le 1000~ gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
long long L, R;
// rad(x): tich cac uoc nguyen to khac nhau cua x. Hai so co cung tap uoc nguyen to <=> cung rad.
long long rad(long long x) {
long long r = 1;
for (long long p = 2; p * p <= x; p++)
if (x % p == 0) {
r *= p;
while (x % p == 0) x /= p;
}
if (x > 1) r *= x;
return r;
}
// Sub 1: R - L <= 1000. Tinh rad cua tung so, dem cap co cung rad bang vet can O(k^2).
void sub1() {
vector<long long> v;
for (long long x = L; x <= R; x++) v.push_back(rad(x));
long long ans = 0;
for (size_t i = 0; i < v.size(); i++)
for (size_t j = i + 1; j < v.size(); j++)
if (v[i] == v[j]) ans++;
cout << ans << "\n";
}
// Sub 2: sang tinh rad[x] cho moi x <= R. Dem so so trong [L, R] co cung rad,
// moi nhom k so cho C(k,2) cap.
void sub2() {
vector<int> rad_arr(R + 1, 1);
for (int p = 2; p <= R; p++)
if (rad_arr[p] == 1) // p la so nguyen to (chua bi so nguyen to nho hon chia het)
for (int m = p; m <= R; m += p) rad_arr[m] *= p;
vector<long long> f(R + 1, 0);
for (long long x = L; x <= R; x++) f[rad_arr[x]]++;
long long ans = 0;
for (long long c : f) ans += c * (c - 1) / 2;
cout << ans << "\n";
}
int main() {
cin >> L >> R;
if (R - L <= 1000) sub1();
else sub2();
return 0;
}
Bình luận