yukicoder : No.1339 循環小数

こういうの地味に手間取る。
https://yukicoder.me/problems/no/1339

問題

正整数Nが与えられる。
1/Nを循環小数で表したとき、その循環節の長さはいくつか。

解法

Nを2倍または5倍しても循環節の長さは変わらない。
そこで、Nの素因数から2と5を取り除いたものをN'とする。
10^K ≡ 1 (mod N')であるような最小のKがこの問題の解となる。

オイラーの定理よりKはφ(N')の約数なので、そのようなKを総当たりし、条件を満たす最小値を求めよう。

int T,N;
ll modpow(ll a, ll n,ll mo) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

int totient(int v) {
	int ret=v;
	for(int i=2;i*i<=v;i++) if(v%i==0) {
		ret=ret/i*(i-1);
		while(v%i==0) v/=i;
	}
	if(v>1) ret=ret/v*(v-1);
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		while(N%2==0) N/=2;
		while(N%5==0) N/=5;
		int t=totient(N);
		int mi=t;
		for(i=1;i*i<=t;i++) if(t%i==0) {
			if(modpow(10,i,N)==1) mi=min(mi,i);
			if(modpow(10,t/i,N)==1) mi=min(mi,t/i);
		}
		cout<<mi<<endl;
		
	}
}

まとめ

わかってしまうとすぐなんだけどね。