有時候真的發覺「成事在天」
Paper的事... 也由不得我擔心太多
先前 Conference paper deadline 跟 ICPC World Finals 撞期了
後來 World Finals 又因為埃及政治事件需要延期...
在我來看，算是好事
2011年2月17日星期四
2010年7月25日星期日
[舊帖] 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 的某個因數
這是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 的某個因數
2010年6月16日星期三
PKU 3696 The Luckiest Number
題意：
給定 L
求 集合 { 8, 88, 888, ... ,888888, ... } 當中 能整除 L 的最小的一個數字
列印該數的長度
算法 ── 思路：
設該數為 88....8，則有方程：
8 × 11....1 ≡ 0 (mod L) -----------(1)
設 g := (8, L)，得：
8/g × 11....1 ≡ 0 (mod L/g) -----------(2)
Case 0: L/g = 1
...
Case 1: L/g 整除 2 或/和 整除 5
11....1 顯然不能整除 2 或/和 整除 5 ⇒ 無解
Case 2: 其他情況
由於 (8/g, L/g) = 1，(2) 可以化簡為：
11....1 ≡ 0 (mod L/g) -----------(3)
以下為最關鍵的一步！
給定 L
求 集合 { 8, 88, 888, ... ,888888, ... } 當中 能整除 L 的最小的一個數字
列印該數的長度
算法 ── 思路：
設該數為 88....8，則有方程：
8 × 11....1 ≡ 0 (mod L) -----------(1)
設 g := (8, L)，得：
8/g × 11....1 ≡ 0 (mod L/g) -----------(2)
Case 0: L/g = 1
...
Case 1: L/g 整除 2 或/和 整除 5
11....1 顯然不能整除 2 或/和 整除 5 ⇒ 無解
Case 2: 其他情況
由於 (8/g, L/g) = 1，(2) 可以化簡為：
11....1 ≡ 0 (mod L/g) -----------(3)
以下為最關鍵的一步！
訂閱：
文章 (Atom)