题解：P10496 The Luckiest Number
QZKago_Req
·
·
题解
题意
给定 L，求 \min\limits_{L\mid\dfrac{8}{9}(10^x-1)}\{x\}。
题解
先推式子：
L\mid\dfrac{8}{9}(10^x-1)
9L\mid8(10^x-1)
\frac{9L}{\gcd(L,8)}\mid10^x-1
10^x\equiv1\pmod{\frac{9L}{\gcd(L,8)}}
根据小学二年级知识，若 a,n 互质，则 \varphi(n)\mid\left(\min\limits_{a^x\equiv1\pmod{n}}\{x\}\right)。
证明可以用反证法。
所以只需求 \varphi\left(\dfrac{9L}{\gcd(L,8)}\right)，枚举其因数，判断是否满足条件即可，时间复杂度 O(\sqrt{L}\log L)。