Hướng dẫn giải của [VTT Q4 Contest 09] Bài 4: Số chính phương [DSQUARE]
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
Đếm số cặp ~(a, b)~ với ~L \le a < b \le R~ sao cho ~a \times b~ có ước chính phương lớn hơn 1, tức là ~a \times b~ không phải số "không chứa bình phương". Điều kiện quan trọng là ~R - L \le 10^3~, nên chỉ có tối đa khoảng 1000 số trong đoạn.
Sub 1: Kiểm tra từng cặp — dùng khi ~R \le 1000~
Với mỗi cặp, tính ~t = a \cdot b~ (không quá ~10^6~) rồi thử mọi ~d \ge 2~ với ~d^2 \le t~ xem ~d^2~ có chia hết ~t~ không. Nếu chỉ nộp sub này: đúng 10/20 test (10 test có ~R~ lớn bị quá thời gian).
Sub 2: Đếm phần bù — ~O((R - L)^2 \log R + \sqrt{R} \cdot (R-L))~
Đếm phần bù: ~a \cdot b~ không đẹp khi và chỉ khi cả ~a~ và ~b~ đều không có ước chính phương lớn hơn 1, đồng thời ~\gcd(a, b) = 1~ (nếu một số nguyên tố ~p~ chia hết cả hai thì ~p^2~ chia hết tích). Các bước:
- Đánh dấu các số trong ~[L, R]~ có ước chính phương: với mỗi ~p = 2, 3, \dots, \lfloor\sqrt{R}\rfloor~, loại các bội của ~p^2~ trong đoạn (chỉ cần ~p^2~ chứ không cần ~p~ nguyên tố).
- Với các số còn lại, đếm số cặp có ~\gcd = 1~.
- Đáp án là tổng số cặp ~\binom{R-L+1}{2}~ trừ đi số cặp vừa đếm.
Bẫy: ~R~ tới ~10^9~ nên tích tới ~10^{18}~, không nên cố kiểm tra trực tiếp tích; dùng long long. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc ~L, R~; ~R \le 1000~ gọi sub1, còn lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước. Chương trình đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
long long L, R;
// Sub 1: R <= 1000 — với mỗi cặp, thử mọi d >= 2 xem d*d có chia hết a*b không
void sub1() {
long long ans = 0;
for (long long a = L; a <= R; a++)
for (long long b = a + 1; b <= R; b++) {
long long t = a * b;
for (long long d = 2; d * d <= t; d++)
if (t % (d * d) == 0) { ans++; break; }
}
cout << ans << "\n";
}
// Sub 2: a*b không đẹp (không có ước chính phương > 1) <=> a, b đều không có
// ước chính phương > 1 và gcd(a,b)=1. Đánh dấu số "sạch" trong [L,R] bằng cách
// loại các bội của p*p (p <= sqrt(R)), rồi đếm cặp sạch nguyên tố cùng nhau.
// Đáp án = tổng số cặp - số cặp sạch nguyên tố cùng nhau.
void sub2() {
int len = R - L + 1;
vector<char> sq(len, 1);
for (long long p = 2; p * p <= R; p++) {
long long q = p * p;
for (long long x = (L + q - 1) / q * q; x <= R; x += q) sq[x - L] = 0;
}
vector<long long> v;
for (int i = 0; i < len; i++) if (sq[i]) v.push_back(L + i);
long long total = (long long)len * (len - 1) / 2, good = 0;
for (size_t i = 0; i < v.size(); i++)
for (size_t j = i + 1; j < v.size(); j++)
if (__gcd(v[i], v[j]) == 1) good++;
cout << total - good << "\n";
}
int main() {
freopen("DSQUARE.INP", "r", stdin);
freopen("DSQUARE.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> L >> R;
if (R <= 1000) sub1();
else sub2();
}
Bình luận