Editorial for Duyên Hải 2020 - Lớp 10 - Bài 2 - Số chính phương
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
~\color{orange}{\text{Cách tiếp cận khác}}~
~\color{green}{\text{Nhận xét}}~
- Phân tích dưới dạng thừa số nguyên tố để tìm quy luật
Khi phân tích các số ~a, b, c~ về dạng ~p_1 ^{f_1} \times p_2 ^{f_2} \times ... \times p_k ^{f_k}~ với ~p_i~ nguyên tố phân biệt, ~k_i~ số mũ nguyên dương
Số chính phương là số có dạng ~p_1 ^{f_1} \times p_2 ^{f_2} \times ... \times p_k ^{f_k}~ với ~p_i~ nguyên tố phân biệt, ~k_i~ số mũ chẵn nguyên dương
Vậy tích của một cặp ~(x, y)~ bất kì là số chính phương ~\Leftrightarrow~ các số mũ ~f_1, f_2, ..., f_k~ của ~x~ và ~y~ đều phải cùng chẵn hoặc cùng lẻ vì khi đó tổng số mũ mỗi nguyên tố đều chẵn.
~\color{orange}{\text{Xử lí}}~
Nếu phải duyệt qua từng bộ ~k~ số mũ thì độ phức tạp rất là cao, nên ta sẽ đưa nó về dạng chung để xử lí nhanh hơn
Ta chỉ quan tâm chẵn lẻ của số mũ, nên không mất tính tổng quát, ta có thể lấy các số mũ modulo cho 2
Với ~x \equiv p \pmod{2} \Leftrightarrow x~ % ~2 = p~
Giả sử có ~x = p_1 ^{f_1} \times p_2 ^{f_2} \times \dots \times p_k ^{f_k}~
Gọi ~mask(x) = p_1 ^{f_1 \% 2} \times p_2 ^{f_2 \% 2} \times ... \times p_k ^{f_k \% 2}~
Khi đó ta có ~mask(x)~ là số nguyên dương nhỏ nhất để ~mask(x) \times x~ là số chính phương
~\color{goldenrod}{\text{Tính toán kết quả}}~
- Duyệt ~a = 1 \rightarrow n~
Gọi ~cnt(mask(a))~ là số lượng số ~j \leq i~ thỏa mãn ~mask(j) = mask(i)~. Khi ráp lại sẽ ra được số chính phương
Tại mỗi vị trí ~i~ có ~f(cnt) = \frac{cnt \cdot (cnt - 1)}{2}~ cách chọn 2 số ~b, c~ còn lại thỏa điều kiện đề bài
Sau khi tính toán nhớ tăng ~cnt(mask(a))~ thêm 1 lần
Khi đó kết quả sẽ là tổng của các ~f(cnt)~ tại mỗi giá trị ~a~
~\color{purple}{\text{Độ phức tạp}}~
Ta có thể sàng nguyên tố trong ~O(n)~
Phân tích thừa số nguyên tố trong ~O(log n)~
Đếm và cập nhật số lượng ~cnt(mask)~ trong ~O(1)~
Đếm được số cách ghép cặp ~f(x)~ trong ~O(1)~
Tính toán trong ~O(n\ log\ max(a))~
Tổng cộng là ~O(n\ log(max(a))~ thời gian và ~O(n)~ bộ nhớ
Tuy nhiên nghe đồn cũng có cách để làm trong ~O(n)~ thời gian bằng cách sàng luôn cả việc tính toán đó bằng một cách ma thuật nào đó
¯\_(ツ)_/¯
~\color{green}{\text{Reference AC Code }}~: Online Solving, Factorization, Sieving, Math, DP_count
~^{^{\color{purple}{\text{Complexity : }} O(n \times log(max(a)))\ \color{purple}{\text{time}}\ ||\ O(n)\ \color{purple}{\text{memory}}}}~
vector<int> prime; /// prime list
vector<int> lpf; /// Lowest prime factor, lpf[x] is smallest prime divisor of x
void sieve(int lim = LIM) /// O(n)
{
prime.assign(1, 2);
lpf.assign(lim + 1, 2);
lpf[1] = 1; /// For easier calculation but can cause inf loops
for (int i = 3; i <= lim; i += 2) {
if (lpf[i] == 2) prime.push_back(lpf[i] = i);
for (int j = 0; j < sz(prime) && prime[j] <= lpf[i] && prime[j] * i <= lim; ++j)
lpf[prime[j] * i] = prime[j];
}
}
/// mask(x) is smallest positive number that mask(x) * x is a perfect square
int getMask(int x) /// O(log n)
{
int mask = 1;
while (x > 1) {
int p = lpf[x], f = 0;
do x /= p, f++; while (p == lpf[x]);
if (f & 1) mask *= p; /// if current power is odd, we mutiple mask with current prime
}
return mask;
}
/// nC2 = number of ways to choose another 2 numbers
ll f(int x) { return 1LL * x * (x - 1) / 2; }
ll magic(int n) /// O(n log max(a))
{
vector<int> cnt(n + 1, 0); /// Save the frequency of each mask
ll res = 0;
for (int a = 1; a <= n; ++a) /// Check all cases of a
res += f(cnt[getMask(a)]++);
return res;
}
int main() /// O(n log max(a))
{
int n;
cin >> n;
sieve(n + 500);
cout << magic(n);
return 0;
}
Comments