POJ 3358

此题的主要还是如何把小数化作分数来解答。

设p/q。对于二进制（三进制，四进制一样），若p>q便商1，取mod，p*2-->p，然后再作p/q，若p<q，商0。

于是有，在去公约数GCD后，p/q的小数是否重复，和上述步骤p是否重复是一致的。若重复，得方程

p*2^i=p*2^j (mod q)。则有p*2^i(2^(j-i)-1)=0 (mod q)。即q|2^i(2^(j-i)-1)。而要求最小，只需使两者相等。即q中2的幂即为i。利用欧拉定理也可求出j-i的最小值。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define LL __int64
using namespace std;

LL fac[10000]; int cnt;

LL gcd(LL a,LL b){
	if(b==0) return a;
	return gcd(b,a%b);
}

LL Euler(LL m){
	LL res=m;
	LL k=(LL)sqrt((double)m);
	for(LL i=2;i<=k;i++){
		if(m%i==0){
			res=res-res/i;
			while(m%i==0)
			m/=i;
		}
	}
	if(m>1)
	res=res-res/m;
	return res;
}

LL quick(LL a,LL b,LL m){
	LL ans=1;
	while(b){
		if(b&1){
			ans=(ans*a)%m;
		}
		b>>=1;
		a=(a*a)%m;
	}
	return ans;
}

int main(){
	LL p,q;
	int kase=0;
	while(scanf("%I64d/%I64d",&p,&q)!=EOF){
		p=p%q;
		LL g=gcd(p,q);
		p/=g; q/=g;
		LL ai=0,aj=0;
		while(q%2==0){
			ai++;
			q/=2;
		}
		LL phi=Euler(q);
		cnt=0;
		LL k=(LL)sqrt((double)phi);
		for(LL i=1;i<=k;i++){
			if(phi%i==0){
				fac[cnt++]=i;
				fac[cnt++]=phi/i;
			}
		}
		sort(fac,fac+cnt);
		for(int i=0;i<cnt;i++){
			LL ans=quick((LL)2,fac[i],q);
			if(ans==1){
				aj=fac[i];
				break;
			}
		}
		printf("Case #%d: %I64d,%I64d
",++kase,ai+1,aj);
	}
	return 0;
}