看板 Prob_Solve 關於我們 聯絡資訊
大家好, 最近參加競賽寫到一題看似簡單 其實有點難度的題目,但現在跟同學討論還是無解 題目大意: 輸入一正整數n, 將會產生一個累加的數m, 例如:n=12, 將會得到m=123456789101112, 最後求m除以2018的餘數為何? 困難點: 1.輸入的n的範圍是在2^64-1之內 2.題目限制時間1秒 如果單純的用累加字串是一定TLE, 因為輸入太大了,光加起來的時間就很長了, 因為輸入太大了,光加起來的時間就很長了, 目前跟同學討論應該是有一種規律, 但我們一直沒想出來, 不知版上有沒有人可以提供解法 感激不盡! ----- Sent from JPTT on my iPhone -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.75.169.104 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1539192492.A.429.html
LPH66: 一個很初階的提示: 長除法10/11 03:21
LPH66: 注意這不是叫你直接寫長除法, 原因如你所說時間是不夠的10/11 03:21
DJWS: 如果位數不變的話,每2018產生循環10/11 09:02
DJWS: 如果位數改變的話,只好用暴力搜尋+預先計算 我猜是這樣10/11 09:03
DJWS: 這題只有log10(2^64-1)=20位數 應該不必預先計算10/11 09:06
ckc1ark: 用3*3的方陣來思考呢 多個[[10^n, 1, 0], [0, 1, 1], [0,10/11 10:13
ckc1ark: 0, 1]] 乘 [1, 1, 1]這樣? n會變大10/11 10:13
ckc1ark: 0, 1]] 乘 [1, 1, 1]這樣? n會變大10/11 10:13
ckc1ark: 抱歉初始應該是[0,1,1]10/11 10:14
pttworld: 這題光是12就有15位,最大千位萬位都有可能10/11 11:05
pttworld: 10*1+90*2+900*3+9000*4+90000*5+900000*6+...10/11 11:08
pttworld: 以上是位數長度10/11 11:08
DJWS: 我說的位數是指0-9皆增加1位數、10-99皆增加2位數10/11 11:38
DJWS: 每種位數分開處理 頂多就20種位數10/11 11:39
DJWS: 1位數、2位數、3位數採用窮舉計算(horner's rule)10/11 11:41
DJWS: 4位數以上,每2018個數字併成一組10/11 11:43
pttworld: 每2018會循環的原理是什麼10/11 21:19
rareone: Ummmm 就我所知這題有兩種寫法10/12 03:37
rareone: 首先是中國剩餘定理的觀察 你可以把數字拆開來 2018 = 210/12 03:38
rareone: * 100910/12 03:38
rareone: 2 的模數很好處理 所以現在關心的是模100910/12 03:39
rareone: 第一種做法:可以發現在同個位數下很有規律 用快速冪解決10/12 03:40
rareone: 這題10/12 03:40
rareone: 我自己在賽中的做法是 dp[目前模數][目前要加的數] 跑一10/12 03:42
rareone: 次 rho 狀態最多1009*1009 種10/12 03:42
rareone: 一旦發現回到之前的狀態10/12 03:44
rareone: 把目前位數還剩下幾步模循環長度10/12 03:44
rareone: 加到答案中10/12 03:44
DJWS: 嚴謹來說是2018*2018會循環 原理就是樓上所述10/12 07:04
ckc1ark: 我的constant space解 https://tinyurl.com/ya9dx59d10/12 12:28
ckc1ark: 我的constant space解 https://tinyurl.com/ya9dx59d10/12 12:28
ckc1ark: 好處是不用考慮modulus會有多大10/12 12:28
ckc1ark: 阿 這就是rareone說的第一種做法吧?10/12 12:50
版上果然有人也參加了,實在沒想到這寫法,感謝各位相助! ※ 編輯: bigload1234 (114.39.29.138), 10/12/2018 14:34:13