大家好，
最近参加竞赛写到一题看似简单
其实有点难度的题目，但现在跟同学讨论还是无解
题目大意：
输入一正整数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说的第一种做法吧?