[舊帖] PKU 2480 Longge's problem

原文位置：http://www.xanga.com/private/editorx.aspx?uid=721833838

這是2010年度 CSC3270 的功課...

---

題意：

給定 N
計算 ∑_1≤i≤Ngcd(i, N)

---

算法：

Ans := 0
Foreach divisor of N, D
　　Ans += D × Phi( N / D )
EndFor

---

證明：

留意到 GCD(i, N) 必然是 N 的某個因數


對於 D | N
GCD(x, N) = D 的必然條件是
x = kD, 其中 k 是正整數

然後
GCD(kD, N) = D ⇔ GCD(k, N / D) = 1

---

實現：

先對 N 進行質因數分解
然後用 DFS 枚舉所有因數 - D

在枚舉 D 的同時
可以利用 歐拉函數 (Euler phi function) 的特性

1. Φ(p^k) = p^k - p^k-1 for prime p
2. Φ(AB) = Φ(A) × Φ(B) for (A, B) = 1

達到 O(1) 更新每個 Φ(N / D)

⇒ 總時間複雜度 = O( # N的因數 )

---

7 void dfs(int k, long long d, int phi) { // phi : PHI(n / d)
8     if (k==q) {
9         ans += d * phi;
10         return;
11     }
12     for (int i=0; i<=e[k]; i++) {
13         dfs(k+1, d, !i?phi:phi-phi/b[k]);
14         d /= b[k];
15         phi *= b[k];
16     }
17 }
...
39         ans = 0;
40         dfs(0, n, 1);
41         printf("%lld\n", ans);

---

延伸 ── 積性函數：

∑_1≤i≤Ngcd(i, N) 積性函數 (Multiplicative function)
即 (a,b) = 1 ⇒  f(ab) = f(a) × f(b)

似曾相識吧？
一個可以令你（？）更好感覺何謂積性的例子... 就是 Euler phi function

---

相關題目 - GCD - Extreme：

• UVa 11424 GCD - Extreme (I)
• UVa 11426 GCD - Extreme (II)

以上兩題要求計算：


我直接沿用 PKU 2480 的 source code
預處理 400000 個答案（每個答案需時 O(因數數目)）
結果跑得很慢... 需時 4.708 sec

──第二個 submission 加了優化：
在 sieve 時給每個數字記錄的一個質因數
從而加快 prime factorization

看見有些人 0.05 sec AC...
應該是用了 multiplicativity

---

GCD - Extreme ── 積性優化：

以上 0.992 sec AC 的程序做了以下的優化：

1. 在 prime sieve 時，為每個數記錄一個質因數
2. 設 gag[N] := ∑_1≤i≤Ngcd(i, N)
   然後利用 multiplicativity 計算之：
   
   • 情況 1) N 是 prime power, i.e., N = p^e (Base case)
     　gag[N] := N × (e+1) - N/p × e（證明從略）
   • 情況 2) N 不是 prime power (其它情況)
     設 p^e | N (e ≥ 1)，其中 e 是對於 p 的最大可能值
     可積性 ⇒ gag[N] = gag[N/p^e] × gag[p^e]
3. 最後，掃描預處理所有答案
   For N := 1 to MAX_N
   　dp[N] := dp[N-1] + gag[N] - N
   EndFor