0168 数字轮换
* * * *
拉格朗日计划
* * * *
数字轮换

把142857的数字右移一位并把最后一个数字7放到最前面,可得714285。

可以验证$714285=5\times 142857$。

这说明142857具有这样一个特殊性质:将其它右移一位并把末位数字移至最前所得的数是它自身的倍数。

考虑大于10且小于$10^{100}$的范围内所有满足这一性质的整数,求它们的和的最后五位数字。

本题难度:



解答

设n是一个满足要求的数,且最后一位数字是d,轮换后的数是原数的x倍,(注意x可以等于1),则显然$(d\times x) \bmod 10$就是d的前一位,不断重复这一过程可得 $$d_{k-1}=(d_k\times x+t) \bmod 10,$$ 其中$d_k$是n中的第k位,t是上一步运算的进位。

因此从末位d开始就可得一序列,只要某一步所得的$d_{k-1}=d$且$t=0$、$d_k\neq0$、且$s$的长度超过1那么就对应一个有效的n。

枚举d和x的所有组合可得结果$59206$。

r=0
for d in range(1,10):
    for x in range(1,10):
        a,t,s=d,0,str(d)
        while len(s) < 101:
            b=a*x+t
            a,t=b%10,b/10
            if a==d and t==0 and len(s)>1 and s[0]!="0":
                r+=int(s[-5:])
            s=str(a)+s

print r%100000