0284 自守数
* * * *
拉格朗日计划
* * * *
自守数

376的平方的末尾就是它本身:$376^2 = 141376$。这样的数称为为自守数。

除十进制以外,其它进制下也存在自守数,例如在14进制下(a、b、c、d分别表示10、11、12、13),c37就是自守数:$c37^2=aa0c37$,它的各位数字之和在14进制下是$c+3+7=18$。

对于$1\le n\le 9$,所有14进制下的n位自守数的各位数字之和为2d8(等于十进制数582)。

求所有14进制下不超过一万位的自守数的各位数字和,答案用14进制表示。

本题难度:



解答

这样的数统称为Automorphic number。

首先可以直接验证,符合题意的一位数是1,7,8。其次,若n是一个符合要求的d位数,那么 $$n^2-n=0 \pmod 14^d$$ 从而$m=14^d+1-n$也符合要求。

最后,若$n_d$是一个符合要求的、能被7整除的d位数,考虑在其前面添加一位a得到的新数$n_{d+1}=a\cdot 14^d+n_d$,则有 $$n_{d+1}^2=(a\cdot 14^d+n_d)^2=a^2\cdot 14^{2d}+2an_d\cdot 14^d+n_d^2=n_d^2 \pmod{14^{d+1}}$$ 由于$n_d^2$模$14^d$等于$n_d$,因此只要 $$a=\frac{n_d^2-n_d}{14^d} \bmod 14,$$ 那么$n_{d+1}$就也符合要求。

按照这一规则从低位到高位生成n,一般而言m与n的各位数字之和是$13(d-1)+15$,但当$a=0$或13时m与n的位数不一致时,为避免遗漏或重复计算,在处理$n_d$时应当只记录所有满足要求的d位数的数字之和。

因此用一个变量z来记录n生成过程中各位数字之和,当$a=13$时计z作为数字和,当$a=0$时则记$13(d-1)+15-z$作为数字和,其他情况都计$13(d-1)+15$作为数字和,如此可得最终结果是$5a411d7b$。

s=1
n=0
a=7
z=0
p=1
for d in range(1,10001):
    z+=a
    if a==0:
        s+=13*(d-1)+15-z
    elif a==13:
        s+=z
    else:
        s+=13*(d-1)+15
    n+=a*p
    p*=14
    a=((n*n-n)/p)%14

x={10:"a",11:"b",12:"c",13:"d"}
r=""
while s:
    d=s%14
    r=x.get(d,str(d))+r
    s=(s-d)/14

print r