真的是好東西~
(I). POJ 2480 Longge's problem (http://poj.org/problem?id=2480)

題目大意: 求 sigma(gcd(i, n)), 1 ≤ i ≤ n.

考慮到枚舉 i 可能會(huì)超時(shí), 我們可以反過(guò)來(lái)枚舉 d | n, 那么答案就是 sigma(d * phi(n / d)).

(II). SPOJ LCMSUM (https://www.spoj.pl/problems/LCMSUM/)

題目大意: 求 sigma(lcm(i, n)), 1 ≤ i ≤ n.

sigma(lcm(i, n)) = n * sigma(i / gcd(i, n)). 同上題一樣, 枚舉 d | n, 問(wèn)題轉(zhuǎn)化為求 sigma(i), gcd(i, n / d) == 1. 可以發(fā)現(xiàn)如果 i 與 n 互質(zhì), 那么 n – i與 n 也互質(zhì). 將互質(zhì)的數(shù)兩兩配對(duì)后答案就是 n / d * phi(n / d) / 2.

(III). SPOJ GCDEX (https://www.spoj.pl/problems/GCDEX/)

題目大意: 求 sigma(gcd(i, j)), 1 ≤ i < j ≤ n.

枚舉 j 后轉(zhuǎn)化為 (I).

(IV). POI Zap (http://www.zybbs.org/JudgeOnline/problem.php?id=1101)

題目大意: 求有多少對(duì) gcd(i, j) == d (i ≤ a, j ≤ b).

令 a’ = a / d, b’ = b / d, 問(wèn)題等價(jià)于求滿(mǎn)足 gcd(i, j) == 1的數(shù)量 (i ≤ a’, j ≤ b’).

定義 F(k) 為 gcd(i, j) ≥ k 的數(shù)量, G(k) 為 gcd(i, j) == k 的數(shù)量.

那么F(k) = (a’ / k) * (b’ / k)

根據(jù)容斥原理有G(1) = F(1) – F(2) – F(3) - F(5) + F(6) …

系數(shù)可以用篩法預(yù)處理, 同時(shí)觀察到對(duì)于連續(xù)的一段 k, F(k) 都是相同的,可以一起算出來(lái). 通過(guò)預(yù)處理系數(shù)的前綴和可以在 O(sqrt(n)) 的時(shí)間算出 G(1).

(V). SPOJ PGCD (https://www.spoj.pl/problems/PGCD/)

題目大意: 求有多少 gcd(i, j) 是質(zhì)數(shù), 1 ≤ i ≤ a, 1 ≤ j ≤ b.

枚舉質(zhì)數(shù) P 后轉(zhuǎn)化為 (IV).

(VI). NOI 2010 能量采集 (http://www.zybbs.org/JudgeOnline/problem.php?id=2005)

題目大意: 求 sigma(gcd(i, j)), i ≤ a, j ≤ b.

Sol 1.

令 F[k] 為滿(mǎn)足 gcd(i, j) == k 的數(shù)量.

那么F[k] = (a / k) * (b / k) – F[2k] – F[3k] – F[4k] …

答案就是 sigma(i * F[i]).

時(shí)間復(fù)雜度 O(n / 1 + n / 2 + n / 3 + …) = O(nlogn).

Sol 2.

枚舉 d = gcd(i, j), a’ = a / d, b’ = b / d, 那么問(wèn)題轉(zhuǎn)化為求滿(mǎn)足 gcd(i, j) == 1(i ≤ a, j ≤ b) 的數(shù)量, 也就轉(zhuǎn)化為 (IV), 將這個(gè)數(shù)量記為 F(a, b).

同時(shí)注意到對(duì)于一段連續(xù)的d, F(a’, b’) 都是一樣的, 可以一起算出來(lái).

時(shí)間復(fù)雜度 O(sqrt(n) * sqrt(n)) = O(n).

(VII). Crash 的數(shù)字表格 (http://www.zybbs.org/JudgeOnline/problem.php?id=2154)

題目大意: 求 sigma(lcm(i, j)) (i ≤ a, j ≤ b).

sigma(lcm(i, j)) = sigma(i * j / gcd(i, j))

枚舉 d = gcd(i, j), 我們只需要對(duì)于所有相同的 d, 計(jì)算出 sigma(i * j).

令 a’ = a / d, b’ = b / d, 那么問(wèn)題轉(zhuǎn)化為求 F(a’, b’) = sigma(i * j) (gcd(i, j) == 1, i ≤ a’, j ≤ b’).

令 Sum(a, b) = 1 * 1 + 1 * 2 + … + a * b, 由等差數(shù)列的求和公式可得:

Sum(a, b) = a * (a + 1) * b * (b + 1) / 4.

根據(jù)容斥原理有F(a, b) =1² * Sum(a / 1, b / 1) - 2² * Sum(a / 2, b / 2) - 3² * Sum(a / 3, b / 3) - 5² * Sum(a / 5, b / 5) + 6² * Sum(a / 6, b / 6)..

注意到對(duì)于一段連續(xù)的 i, Sum(a / i, b / i) 是相同的, Sum 的系數(shù)也可以通過(guò)篩法預(yù)處理出來(lái).

最后, 對(duì)于一段連續(xù)的 d, F(a’, b’) 也是相同的, 可以一起算出來(lái).

時(shí)間復(fù)雜度 O(sqrt(n) * sqrt(n)) = O(n).

擴(kuò)展閱讀

線性篩法: http://www.shnenglu.com/sdfond/archive/2009/03/16/76775.html

四道Gcd統(tǒng)計(jì)問(wèn)題: http://hi.baidu.com/廣陵lonely散/blog/item/6b00f8de2ca366b7cd11669e.html