問題概要
$T$ 個のクエリ毎に $N$ が与えられるので以下について求めたい。
$ \frac{1}{N}$ を循環小数で表した時の循環節の長さ
制約
$ 1 \leqq T \leqq 100$
$ 1 \leqq N \leqq 10^{9}$
解法
分母の値にに2や5をかけても循環節の長さは変わらないので、予め分母の値を2と5で割れるだけ割っておくものとする。
ここで最小とは限らない循環節の長さ $K$ について $10^{K} \equiv 1 (\bmod N)$ が、$K$ が循環節の長さであることと同値。
従って上式を満たす最小の自然数 $K$ を求める問題に言い換えることができる。
ところで $\varphi (n)$ をオイラーのトーシェント関数として
$$ 10^{\varphi(N)} \equiv 1 \bmod N $$
が成立する。
従って $K$ の候補として $\varphi(N)$ の約数を全て調べればよい(この制約下で約数の個数の最大値は1344個なので約数を全探索してOK)。
これで1テストケース当たり $O(\sqrt{N})$ で解くことが出来た。
実装
#include <bits/stdc++.h> using namespace std; typedef long long int ll; template<typename T> T euler_phi(T n){ T res=n; for(T i=2;i*i<=n;++i){ if(n%i==0){ res-=res/i; while(n%i==0)n/=i; } } if(n>1)res-=res/n; return res; } template<typename T> vector<T> divisor(T n){ vector<T> res; for(T i=1;i*i<=n;++i){ if(n%i==0){ res.emplace_back(i); if(i!=n/i)res.emplace_back(n/i); } } return res; } ll mod_pow(ll x,ll n,ll Mod){ x%=Mod; ll res=1; while(n>0){ if(n&1LL)res=res*x%Mod; x=x*x%Mod; n>>=1LL; } return res; } int solve(int n){ while(n%2==0)n/=2; while(n%5==0)n/=5; int res=n; for(int d:divisor(euler_phi(n))){ if(mod_pow(10,d,n)==1){ res=min(res,d); } } return res; } int main(){ int q; cin >> q; while(q--){ int n; cin >> n; cout << solve(n) << "\n"; } }
補足
上で紹介したオイラーの定理の証明
始めに次の補題を示す。
$p$ を素数とし $a$ を $p$ と互いに素な整数とすると任意の自然数 $n$ に対して
$$ a^{(p-1) p^{n-1}} \equiv 1 \quad\left(\bmod p^{n}\right) $$
(証明)
$n$ に関する数学的帰納法を用いて示す。
$n=1$ の場合はフェルマーの小定理そのもの
$n$ の場合において上の補題が成り立つと仮定すると
$$ a^{(p-1) p^{n-1}}=1+p^{n} k \quad(k \in \boldsymbol{Z}) $$
この両辺を $p$ 乗すると
$$ a^{(p-1) p^{n}}=\left(1+p^{n} k\right)^{p}=1+p \cdot p^{n} k+\sum_{j=2}^{p} \binom{p}{j} p^{j n} k^{j} \equiv 1 \quad\left(\bmod p^{n+1}\right) $$
となりこれは $n+1$ の時に成立することを示している
$\varphi\left(p^{n}\right)=(p-1) p^{n-1}$ より上の補題の式は次のように書き換えることができる
$$ a^{\varphi\left(p^{n}\right)} \equiv 1\left(\bmod p^{n}\right) $$
各素因数についてこれが成り立つことからオイラーの定理が導かれる。
