设各个数位依次是$a_0,a_1,a_2,a_3,a_4$,注意到重排后$a_2$不变,因此实际只需计算最大和最小数字之差,以及次大和次小数字之差,而在b进制下这两者的轨道长度都是有限的。
先计算出各数字对的轨道,接下来缓存各数字的Kaprekar路径长度逐个搜索即可,最终结果是$552506775824935461$。
注:因数据量较大,代码中还打印了进度信息。
target=300
mod=10**18
res=0
for k in range(2,target+1):
x=6*k+3
counts=[[0]*(i+1) for i in range(x)]
for u0 in range(x):
for v0 in range(u0+1):
if counts[u0][v0]==0:
cnt=1
chain=[]
u,v=u0,v0
while True:
chain.append((u,v))
if u==0:
break
if v==0:
u1,v1=x-u,u-1
if v1>u1:
u1,v1=v1,u1
else:
d0,d1,d2,d3=sorted((u,v-1,x-u,x-1-v))
u1,v1=x-1-d0, d3-d1
if u1==u and v1==v:
break
if counts[u1][v1]:
cnt+=counts[u1][v1]
break
u,v=u1,v1
cnt+=1
for u,v in chain:
counts[u][v]=cnt
cnt-=1
print k,"completed"
res+=(sum(10*(x-u)*((2*u-1)*counts[u][0]+(3*u-1)*counts[u][u]+sum((12*v*(u-v)-2)*counts[u][v] for v in range(1, u))) for u in range(1,x))-1)%mod
print res%mod
|