http://noip.ybtoj.com.cn/contest/802/problem/7
对 n n n 进行一些简单处理,现在相当于变成了一个 n ′ n' n′ 和 11111 … 111 11111\dots 111 11111…111 的关系。
考虑这个东西不好表示,我们可以用 1 0 l − 1 9 \dfrac{10^l-1}9 910l−1 来表示,现在变成了:
9 n ′ = 1 0 l − 1 9n'=10^l-1 9n′=10l−1,也就是 1 0 l ≡ 1 ( m o d 9 n ′ ) 10^l\equiv 1\pmod {9n'} 10l≡1(mod9n′)
记 m = 9 n ′ m=9n' m=9n′,一个合法的构造是 l = φ ( m ) l=\varphi (m) l=φ(m),但我们要求最小 l l l,所以我们枚举 φ ( m ) \varphi(m) φ(m) 的所有因子即可。