a2−a=a(a−1)なので、a=kは条件を満たす。よって、解が存在しないことはありえない。しかし、a=2,3,⋯kと全て順番に調べると、計算量が最大でO(k)になってしまうので、他の解法を考える。
k≥2より、kは最低でも1つの素因数を持つ。そのうちの1つをpとし、kは素因数pをn個持つとする。ユークリッドの互除法により、gcd(a,a−1)=gcd(a−1,1)=1
なので、aとa−1が両方とも素因数pを持つことはない。よって、aとa−1のうちどちらか一方のみが素因数pをn個持つ、すなわちpnの倍数である。
kの持つ他の素因数についても同様のことが成り立つので、kの持つ素因数の種類数をmとすると、kの持つ全ての素因数をaとa−1に割り当てる方法は2m通りとなる。
それぞれの割り当て方について、a,a−1に割り当てられた素因数の積をそれぞれM,Nとすると、a=Mx,a−1=Ny(x,yは整数)と書ける。2式からaを消去するとMx−Ny=1となるので、Mx≡1(mod N) よって、Mのmod Nにおける逆元をx0(0≤x0<N)とすると、x≡x0(mod N)
なのでa=Mx=kl+Mx0(lは整数)と書ける。a≥2であるから、aの最小値は、Mx0≥2ならばMx0, そうでないならk+Mx0となる。(MとNには共通素因数がないので、Mのmod Nにおける逆元は常に存在する。逆元についてはこちらを参照。)
kに対する素数判定はO(k)で行える。また、小さい方からn番目までの全素数の積をPnとおくと、P12>1012なので、この問題の制約ではm≤11となる。よって、O(2m)でもTLEの心配はない。
(参考)本問は、東京大学2005年度学部入試の理系数学第4問を一般化したものである。
質問・誤りがある場合
Twitterに連絡ください。ID : @YS55749378