# sum of gcd

## 想辦法把 contribute 的概念講清楚

- 題目是要求 sum of gcd(i, n) for i = 1~target
- $\Sigma_1^{target} gcd(i, n)$
- 我們知道 gcd(12, i) 長下面這樣，有沒有辦法透過因數來讓我們算快一點 O(n)->O(factor)

---

- 以因數 2 為例，對所有被 2 整除的數 x，gcd(x, 2) >= 2
- 可以把 approximate contribute of 2 設成 2
- $contribute(2)^*=2$
- 並且我們可以用 n / 2 得到被 2 整除的數字數量，將其乘以 2 的估計貢獻 2，做一個因數 2 對 sum of gcd 的大致貢獻估計
- $total\ contribute(2)^* = n/2*contribute(2)^*$

---

- 以相同的想法來看 4 會發現，如果有數字同時被因數 2, 4 整除，那我們會高估因數 4 對這些數的貢獻
- 因為因數 2 已經確定 gcd(x, 2) >= 2 了，因數 4 確定 gcd(x, 4) >= 4 實際上只多貢獻了 gcd(x, 4) - gcd(x, 2) = 2 而已
- 為了避免重複計算這些因數間的貢獻值，因此延伸出一種因數對 gcd 的實際貢獻值的概念

---

- 每個因數 x 的實際貢獻值，需要透過自身扣掉自己的因數的實際貢獻值來得到
- contribute(x) = x - sum of actual contribute(y) for y can divide x
- $contribute(x)=x-\Sigma \ contribute(y)$, where x mod y = 0
- contribute(1) = 1
- contribute(2) = 2 - contribute(1)
- contribute(3) = 3 - contribute(1)
- contribute(4) = 4 - contribute(1) - contribute(2)
- contribute(6) = 6 - contribute(1) - contribute(2) - contribute(3)
- contribute(12) = 12 - contribute(1) - contribute(2) - contribute(3) - contribute(4) - contribute(6)

---

- 而 gcd(12, x) 的值可以由 sum of actual contribute(y) for y can divide x 來獲得
- $gcd(12, x) = \Sigma \ contribute(y)$, where x mod y = 0
- 如 4 可以被 1, 2, 4 整除， gcd(12, 4) = contribute(1) + contribute(2) + contribute(4)

---

- 根據上面實際貢獻度的引入，我們可以放心的計算因數 x 對 sum of gcd(n, i) for i = 1 ~ target 的總貢獻
- total contribute(1) = target / 1 * contribute(1) = target / 1 * 1
- total contribute(2) = target / 2 * contribute(2) = target / 2 * 2
- total contribute(3) = target / 3 * contribute(3) = target / 3 * 2
- total contribute(4) = target / 4 * contribute(4) = target / 4 * 2
- total contribute(6) = target / 6 * contribute(6) = target / 6 * 2
- total contribute(12) = target / 12 * contribute(12) = target / 12 * 4

---

- 結論
- 成功把複雜度壓到 O(factor)
- 只是在預處理實際貢獻度的時候需要 O(factor ^ 2)