大家好，
最近參加競賽寫到一題看似簡單
其實有點難度的題目，但現在跟同學討論還是無解
題目大意：
輸入一正整數n,
將會產生一個累加的數m,
例如：n=12,
將會得到m=123456789101112,
最後求m除以2018的餘數為何？
困難點：
1.輸入的n的範圍是在2^64-1之內
2.題目限制時間1秒
如果單純的用累加字串是一定TLE，
因為輸入太大了，光加起來的時間就很長了，
因為輸入太大了，光加起來的時間就很長了，
目前跟同學討論應該是有一種規律，
但我們一直沒想出來，
不知版上有沒有人可以提供解法
感激不盡！

一個很初階的提示: 長除法注意這不是叫你直接寫長除法, 原因如你所說時間是不夠的

如果位數不變的話，每2018產生循環如果位數改變的話，只好用暴力搜尋+預先計算 我猜是這樣這題只有log10(2^64-1)=20位數 應該不必預先計算

用3*3的方陣來思考呢 多個[[10^n, 1, 0], [0, 1, 1], [0,0, 1]] 乘 [1, 1, 1]這樣? n會變大抱歉初始應該是[0,1,1]

這題光是12就有15位，最大千位萬位都有可能10*1+90*2+900*3+9000*4+90000*5+900000*6+...以上是位數長度

我說的位數是指0-9皆增加1位數、10-99皆增加2位數每種位數分開處理 頂多就20種位數1位數、2位數、3位數採用窮舉計算(horner's rule)

每2018會循環的原理是什麼

Ummmm 就我所知這題有兩種寫法首先是中國剩餘定理的觀察 你可以把數字拆開來 2018 = 2* 10092 的模數很好處理 所以現在關心的是模1009第一種做法：可以發現在同個位數下很有規律 用快速冪解決這題我自己在賽中的做法是 dp[目前模數][目前要加的數] 跑一次 rho 狀態最多1009*1009 種一旦發現回到之前的狀態把目前位數還剩下幾步模循環長度加到答案中

嚴謹來說是2018*2018會循環 原理就是樓上所述

我的constant space解 https://tinyurl.com/ya9dx59d我的constant space解 https://tinyurl.com/ya9dx59d好處是不用考慮modulus會有多大阿 這就是rareone說的第一種做法吧?