Editorial for Số chính phương (DHBB CT)
Submitting an official solution before solving the problem yourself is a bannable offence.
Authors:
\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}
\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}
\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}
\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
hay