[舊帖] 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 的某個因數