Tóm tắt đề bài

Cho \(n\) (\(1 \le n \le 10^6\)). Đếm số cặp \((a,b)\) sao cho:

• \(1 \le a < b \le n\)
• \(a \cdot b\) là một số chính phương.

Kết quả lấy modulo \(10^9 + 7\).

Phân tích

Điều kiện \(a\cdot b\) là chính phương tương đương với mọi số mũ của các thừa số nguyên tố trong phân tích của \(a\cdot b\) đều chẵn.

Một cách nhìn chuẩn là đưa mỗi số về “phần tự do bình phương” (square-free part):

• Viết \(x = s \cdot t^2\) với \(s\) là square-free.
• Khi đó \(a\cdot b\) là chính phương \(\Leftrightarrow\) \(sf(a) = sf(b)\) (cùng square-free part).

Nếu làm theo nhóm square-free part, ta cần đếm số phần tử trong từng nhóm rồi cộng \(\binom{k}{2}\), nhưng tính square-free part cho mọi số đến \(n\) vẫn làm được \(O(n \log \log n)\).

Tuy nhiên code AC dùng một công thức số học khác dựa trên hàm Euler \(\varphi\):

Nhận xét then chốt dẫn tới công thức trong code

Giả sử \(a<b\) và \(ab\) là chính phương. Đặt \(g=\gcd(a,b)\), viết:

• \(a = g x\)
• \(b = g y\)
• \(\gcd(x,y)=1\)

Khi đó:

Vì \(g^2\) đã là chính phương nên điều kiện \(ab\) chính phương tương đương \(xy\) là chính phương. Nhưng \(\gcd(x,y)=1\), tích \(xy\) là chính phương chỉ khi cả \(x\) và \(y\) đều là chính phương. Do đó đặt:

• \(x=u^2\)
• \(y=v^2\)
• \(\gcd(u,v)=1\)
• và vì \(a<b\) nên \(u<v\)

Suy ra mọi cặp hợp lệ có dạng:

Ràng buộc \(b \le n\) trở thành:

Với một \(v\) cố định, số cách chọn \(u\) sao cho \(1 \le u < v\) và \(\gcd(u,v)=1\) chính là \(\varphi(v)\).

Vậy tổng số cặp là:

Đây đúng là thứ code đang tính (dùng biến p thay cho \(v\)).

Hướng giải quyết

Ý tưởng

• Ta cần tính \(\varphi(p)\) cho mọi \(p \le \lfloor \sqrt{n} \rfloor\).
• Sau đó cộng dồn \(\varphi(p)\cdot \left\lfloor \frac{n}{p^2} \right\rfloor\) với \(p\) từ \(2\) đến \(\lfloor \sqrt{n}\rfloor\).
• Lấy modulo \(10^9+7\).

Tính \(\varphi\) bằng sàng (sieve)

Code dùng sàng Euler phi cơ bản:

1. Khởi tạo euler[i] = i.
2. Với mỗi số nguyên tố \(x\) (nhận biết bởi euler[x] == x):
   • Với mọi bội \(j\) của \(x\): euler[j] -= euler[j] / x.

Sau đó euler[p] chính là \(\varphi(p)\).

Khớp với code AC

• sieve_phi(ceil(sqrt(n)+1)+1) đảm bảo mảng phi đủ đến khoảng \(\sqrt{n}\).

• Vòng lặp:

  • for (int p = 2; p * p <= n; ++p)
    • cộng 1LL * euler[p] * (n / (p * p))

• Lưu ý kiểu long long để tránh tràn khi nhân.

• Cuối cùng res %= MOD.

Các lỗi hay gặp

• Quên điều kiện \(\gcd(u,v)=1\) dẫn tới đếm thừa (vì khi đó \(xy\) có thể là chính phương nhưng không suy ra từng cái là chính phương nếu không coprime).
• Tràn số khi tính p*p hoặc khi nhân phi * (n/(p*p)) (cần long long).
• Tính \(\varphi\) đến \(n\) thay vì đến \(\sqrt{n}\) gây tốn hơn không cần thiết.

Độ phức tạp

• Thời gian:
  • Sàng phi đến \(m=\lfloor \sqrt{n} \rfloor\): \(O(m \log \log m)\) (thực tế gần \(O(m \log \log m)\)).
  • Vòng lặp tổng: \(O(m)\).
• Bộ nhớ: \(O(m)\) cho mảng euler.

Với \(n \le 10^6\) thì \(m \le 1000\), chạy rất nhanh.

Code tham khảo

#include <iostream>
#include <cstring>
#include <numeric>
#include <cmath>

using namespace std;

const int MOD = 1e9 + 7;
const int LIM = 1e7 + 17;
const int SQRT_LIM = ceil(sqrt(LIM) + 1) + 1;

int euler[SQRT_LIM];

// Sàng tính phi Euler cho mọi số từ 0..n
void sieve_phi(int n)
{
    iota(euler, euler + n + 1, 0);
    for (int x = 2; x <= n; x++) if (euler[x] == x) // x là số nguyên tố
        for (int j = x; j <= n; j += x)
            euler[j] -= euler[j] / x;
}

int solve(int n)
{
    int m = ceil(sqrt(n) + 1) + 1;
    sieve_phi(m);

    long long res = 0;
    // Tổng: sum_{p=2..sqrt(n)} phi(p) * floor(n / p^2)
    for (int p = 2; 1LL * p * p <= n; ++p)
        res += 1LL * euler[p] * (n / (p * p));

    res %= MOD;
    return (int)res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    cout << solve(n);
    return 0;
}