首页 > 代码库 > POJ 3358

POJ 3358

2024-07-22 07:47:38   212人阅读

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

设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 __int64using 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\n",++kase,ai+1,aj);	}	return 0;}

　　

POJ 3358


联系
我们