此题的主要还是如何把小数化作分数来解答。
设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#include #include #include #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
