問題描述

第一象限（含軸）格點 (x,y)，0≤x,y≤N，不含原點。格點可見 ⇔ 連線不經過其他格點 ⇔ gcd(x,y)=1。求可見格點總數。N≤1000，多測試用例。

數學推導

可見格點 = 軸上點 + 內部點。
軸上：(1,0),(0,1) 共 2 個（gcd(x,0)=x，只有 x=1 可見）。
內部：x,y ≥ 1，gcd(x,y)=1。
對固定 x，y=1..N 中與 x 互質的個數 = φ(x)（若 N≥x）。但 y 也限制 ≤N。
實際上：Σ_{x=1..N} Σ_{y=1..N} [gcd(x,y)=1] = 2·Σ_{i=1..N} φ(i) - 1。
加上軸上 2 個：總數 = 2·Σ_{i=1..N} φ(i) + 1。

驗證：N=2 → φ(1)=1, φ(2)=1 → 2*(1+1)+1=5。樣例 2→5 正確。

線性篩法預計算 φ 前綴和

const int MAXN = 1000;
int phi[MAXN+1], primes[MAXN+1], pcnt;
bool vis[MAXN+1];
long long sum_phi[MAXN+1];

void linear_sieve() {
    phi[1] = 1;
    for (int i=2; i<=MAXN; ++i) {
        if (!vis[i]) { primes[pcnt++]=i; phi[i]=i-1; }
        for (int j=0; j

關鍵細節

線性篩 O(N)：同時得到質數表與 φ 值，N=1000 瞬間完成。
φ 遞推公式：

  i % p == 0 → phi[i*p] = phi[i] * p

  i % p != 0 → phi[i*p] = phi[i] * (p-1)
前綴和：sum_phi[i] 直接回答查詢。
長整型：N=1000 時答案 ≈ 304,193，int 足夠，但習慣用 long long。


複雜度

預處理：O(MAXN) = 1000。
查詢：O(1)。


總結
PKU 3090 是歐拉函數 φ(n) 的直接應用題。關鍵數學洞察：可見格點數 = 2·Σφ(i) + 1。線性篩法同時計算 φ 表與前綴和，查詢 O(1)。此題是「數論函數預計算 + 前綴和答查詢」的教科書級範例。掌握線性篩 φ 計算，所有涉及互質計數的問題（如分數個數、可見點、約數和等）均可高效解決。