由于数据范围非常大，逐个检验显然是不可取的。
以下实现使用的是该页面的算法。
设$10^n-1=ab$且$\gcd(a,b)=1$，设a'是a在模b乘法群中的逆，即$aa'=1\bmod b$，那么$aa'$就是一个Kaprekar数，并且除了$1$和形如$10^k-1$的数以外的所有Kaprekar数均在此法生成的数中。
n依次取2到8，枚举$10^n-1$的约数，并用辗转相除法计算a'，最后筛出不超过25000000的数即可。
本题第一名的代码非常短，不清楚是怎么实现的。
最终代码有七行。
代码长度：308字节 vs. 全站第一：70字节。
import itertools as r
def g(a,b):
if b<1:return 1,0,a
x,y,d=g(b,a%b)
return y,x-(a//b)*y,d
t=[10**i-1for i in range(1,9)]
*map(print,filter(lambda x:x<25000000,sorted(set([1]+t+[*r.chain(*[[a*(g(a,b)[0]%b),b*(g(b,a)[0]%a)]for n in t for a in range(2,int(n**0.5)+1)if a*(b:=n//a)==n and g(a,b)[2]<2])])))),
|
