yukicoder 1339 循環小数
まず, 重要な定理を挙げる.
定理1: $ Kが$ \frac{1}{N}を循環小数に直した時の周期であることは$ 10^K \equiv 1 \pmod Nであることと同値
また, 次の定理も成り立つ.
定理2: $ a, Nについて, 互いに素ならば$ a^{\phi(N)} \equiv 1 \pmod Nである.
この問題では$ a = 10とする.
以上の定理より, あらかじめNを2と5で割れるだけ割っておいて(これは定理2を使うため), $ \phi(N)を素因数分解を用いて求め, その約数を列挙することによって解くことができる. 計算量は$ O(\sqrt N)となる.