鐪熺殑鏄ソ涓滆タ~
(I). POJ 2480 Longge's problem (http://poj.org/problem?id=2480)
棰樼洰澶ф剰: 姹?/span> sigma(gcd(i, n)), 1 ≤ i ≤ n.
鑰冭檻鍒版灇涓?/span> i 鍙兘浼氳秴鏃?/span>, 鎴戜滑鍙互鍙嶈繃鏉ユ灇涓?/span> d | n, 閭ｄ箞絳旀灝辨槸 sigma(d * phi(n / d)).
(II). SPOJ LCMSUM (https://www.spoj.pl/problems/LCMSUM/)
棰樼洰澶ф剰: 姹?/span> sigma(lcm(i, n)), 1 ≤ i ≤ n.
sigma(lcm(i, n)) = n * sigma(i / gcd(i, n)). 鍚屼笂棰樹竴鏍?/span>, 鏋氫婦 d | n, 闂杞寲涓烘眰 sigma(i), gcd(i, n / d) == 1. 鍙互鍙戠幇濡傛灉 i 涓?/span> n 浜掕川, 閭ｄ箞 n – i涓?/span> n 涔熶簰璐?/span>. 灝嗕簰璐ㄧ殑鏁頒袱涓ら厤瀵瑰悗絳旀灝辨槸 n / d * phi(n / d) / 2.
(III). SPOJ GCDEX (https://www.spoj.pl/problems/GCDEX/)
棰樼洰澶ф剰: 姹?/span> sigma(gcd(i, j)), 1 ≤ i < j ≤ n.
鏋氫婦 j 鍚庤漿鍖栦負 (I).
(IV). POI Zap (http://www.zybbs.org/JudgeOnline/problem.php?id=1101)
棰樼洰澶ф剰: 姹傛湁澶氬皯瀵?/span> gcd(i, j) == d (i ≤ a, j ≤ b).
浠?/span> a’ = a / d, b’ = b / d, 闂絳変環浜庢眰婊¤凍 gcd(i, j) == 1鐨勬暟閲?/span> (i ≤ a’, j ≤ b’).
瀹氫箟 F(k) 涓?/span> gcd(i, j) ≥ k 鐨勬暟閲?/span>, G(k) 涓?/span> gcd(i, j) == k 鐨勬暟閲?/span>.
閭ｄ箞F(k) = (a’ / k) * (b’ / k)
鏍規嵁瀹規枼鍘熺悊鏈?/span>G(1) = F(1) – F(2) – F(3) - F(5) + F(6) …
緋繪暟鍙互鐢ㄧ瓫娉曢澶勭悊, 鍚屾椂瑙傚療鍒板浜庤繛緇殑涓孌?/span> k, F(k) 閮芥槸鐩稿悓鐨?/span>,鍙互涓璧風畻鍑烘潵. 閫氳繃棰勫鐞嗙郴鏁扮殑鍓嶇紑鍜屽彲浠ュ湪 O(sqrt(n)) 鐨勬椂闂寸畻鍑?/span> G(1).
(V). SPOJ PGCD (https://www.spoj.pl/problems/PGCD/)
棰樼洰澶ф剰: 姹傛湁澶氬皯 gcd(i, j) 鏄川鏁?/span>, 1 ≤ i ≤ a, 1 ≤ j ≤ b.
鏋氫婦璐ㄦ暟 P 鍚庤漿鍖栦負 (IV).
(VI). NOI 2010 鑳介噺閲囬泦 (http://www.zybbs.org/JudgeOnline/problem.php?id=2005)
棰樼洰澶ф剰: 姹?/span> sigma(gcd(i, j)), i ≤ a, j ≤ b.
Sol 1.
浠?/span> F[k] 涓烘弧瓚?/span> gcd(i, j) == k 鐨勬暟閲?/span>.
閭ｄ箞F[k] = (a / k) * (b / k) – F[2k] – F[3k] – F[4k] …
絳旀灝辨槸 sigma(i * F[i]).
鏃墮棿澶嶆潅搴?/span> O(n / 1 + n / 2 + n / 3 + …) = O(nlogn).
Sol 2.
鏋氫婦 d = gcd(i, j), a’ = a / d, b’ = b / d, 閭ｄ箞闂杞寲涓烘眰婊¤凍 gcd(i, j) == 1(i ≤ a, j ≤ b) 鐨勬暟閲?/span>, 涔熷氨杞寲涓?/span> (IV), 灝嗚繖涓暟閲忚涓?/span> F(a, b).
鍚屾椂娉ㄦ剰鍒板浜庝竴孌佃繛緇殑d, F(a’, b’) 閮芥槸涓鏍風殑, 鍙互涓璧風畻鍑烘潵.
鏃墮棿澶嶆潅搴?/span> O(sqrt(n) * sqrt(n)) = O(n).
(VII). Crash 鐨勬暟瀛楄〃鏍?/span> (http://www.zybbs.org/JudgeOnline/problem.php?id=2154)
棰樼洰澶ф剰: 姹?/span> sigma(lcm(i, j)) (i ≤ a, j ≤ b).
sigma(lcm(i, j)) = sigma(i * j / gcd(i, j))
鏋氫婦 d = gcd(i, j), 鎴戜滑鍙渶瑕佸浜庢墍鏈夌浉鍚岀殑 d, 璁＄畻鍑?/span> sigma(i * j).
浠?/span> a’ = a / d, b’ = b / d, 閭ｄ箞闂杞寲涓烘眰 F(a’, b’) = sigma(i * j) (gcd(i, j) == 1, i ≤ a’, j ≤ b’).
浠?/span> Sum(a, b) = 1 * 1 + 1 * 2 + … + a * b, 鐢辯瓑宸暟鍒楃殑姹傚拰鍏紡鍙緱:
Sum(a, b) = a * (a + 1) * b * (b + 1) / 4.
鏍規嵁瀹規枼鍘熺悊鏈?/span>F(a, b) =12 * Sum(a / 1, b / 1) - 22 * Sum(a / 2, b / 2) - 32 * Sum(a / 3, b / 3) - 52 * Sum(a / 5, b / 5) + 62 * Sum(a / 6, b / 6)..
娉ㄦ剰鍒板浜庝竴孌佃繛緇殑 i, Sum(a / i, b / i) 鏄浉鍚岀殑, Sum 鐨勭郴鏁頒篃鍙互閫氳繃絳涙硶棰勫鐞嗗嚭鏉?/span>.
鏈鍚?/span>, 瀵逛簬涓孌佃繛緇殑 d, F(a’, b’) 涔熸槸鐩稿悓鐨?/span>, 鍙互涓璧風畻鍑烘潵.
鏃墮棿澶嶆潅搴?/span> O(sqrt(n) * sqrt(n)) = O(n).
鎵╁睍闃呰
綰挎х瓫娉?/span>: http://www.shnenglu.com/sdfond/archive/2009/03/16/76775.html
鍥涢亾Gcd緇熻闂: http://hi.baidu.com/騫塊櫟lonely鏁?/span>/blog/item/6b00f8de2ca366b7cd11669e.html
]]>
[Sdoi2011]娑堣楁垬: 寰堢患鍚堢殑涓閬撻.鍙互鐪嬪嚭鏉ユ槸鏍戜腑鐨勬渶灝忓壊.涓ょ鍋氭硶:1)澧炲姞涓涓眹鐐?灝嗘瘡涓闂畾鐐硅繛姹?瀹歸噺INF.瀹炵幇濂界殑link_cut tree緇存姢鏈澶ф祦鑳借窇榪囧幓.2)鐩存帴鎬濈淮鐨勮瘽鍘繪帀鐨勮竟鑲畾鏄竴浜涚偣鐨凩CA鍒版牴鐨勬渶灝忓?閭ｄ箞灝辨妸鎵鏈夌殑鐐瑰垎緇?鐢ㄥ姩鎬佽鍒掑幓鍋?鍗曡皟鏍堢淮鎶?
2010.7.25浠庢暟瀛﹀浠よ惀鍥炴潵,鏅嬬駭闂涓嶅ぇ
[2010鍥藉闆嗚闃焆紼沖畾濠氬Щ:鍏堝啓浜嗕竴涓毚鍔涚綉緇滄祦,鐒跺悗鎬葷粨澧炲箍璺殑褰㈠紡,鑶滄嫓鎴戞牎鐨勫皬鍚屽
]]>
[璁＄畻鏈烘淇甝 heap
[鑸嚎瀵艱埅] POJ鐨勫師棰?楦ｈ阿:Foreverbell).璁綟[s][c]鍦╯鐐規湁c鐨勬渶灝忚姳璐?緇存姢榪欎釜涓滆タ灝卞彲浠ヤ簡
]]>
COURIER:鐘舵佸帇緙╃殑鍔ㄦ佽鍒?f[S][Bx]琛ㄧず浜哄凡緇忓畬鎴愪簡S闆嗗悎涓殑浠誨姟,褰撳墠鍦ㄤ換鍔鐨勭粨鏉熶綅緗瓸x鏃剁殑mindist.
f[S|(1<<y)][By]=min{f[S][Bx]+dist(Bx,Ay)+dist(Ay+By)} 鏈鍚庢壂鎻忕瓟妗堟椂娉ㄦ剰榪樿鍥炲埌婧愮偣
]]>