給定有理數(shù)P/Q，求它的二進(jìn)制小數(shù)的循環(huán)節(jié)長(zhǎng)度。
先把這個(gè)分?jǐn)?shù)化為既約分?jǐn)?shù)，則循環(huán)節(jié)開始的位置M是使?jié)M足2^M | Q的最大M。令Q1=Q/2^M,則循環(huán)節(jié)的長(zhǎng)度就是求最小的N使2^N模Q1為1。這個(gè)問題好像沒有有效的解法（關(guān)于Q1的位數(shù)為多項(xiàng)式級(jí)別）。由于2和Q1互素，可以用歐拉定理來解。即2^phi（Q1）對(duì)Q1同余1。所求的N一定是phi（Q1）的一個(gè)因子，先分解Q1，再分解phi（Q1），遞歸枚舉phi（Q1）的所有因子，快速取冪算之，找到最小的滿足要求的phi（Q1）的因子即為所求。
只是異常繁瑣，而且分解因子要生成素?cái)?shù)表，對(duì)時(shí)空要求都較高，不知有什么更佳的辦法。
/**//*Problem: 3358 User: y09shendazhi
Memory: 3620K Time: 47MS
Language: C++ Result: Accepted
Source Code */
#include <iostream>
#include<algorithm>
using namespace std;
__int64 PrimeFactor[100];//因子
__int64 Cnt;
__int64 P,Q;
__int64 ans1,ans2;//輸出結(jié)果
__int64 Factor;//遞歸尋找因子的時(shí)候用到
const __int64 INF=1000000000000000;
const __int64 MAXN=400000;
__int64 isCom[MAXN];//
__int64 Prime[MAXN];//素?cái)?shù)表
void getPrime()//線性生成400000以內(nèi)的素?cái)?shù)
{
__int64 num=0;
__int64 i,j;
__int64 temp=0;
for(i=2;i<MAXN;i++)
{
if(!isCom[i])
Prime[num++]=i;
for(j=0;j<num&&(temp=i*Prime[j])<MAXN;j++)
{
isCom[temp]=1;
if(!(i%Prime[j]))
break;
}
}
}
__int64 FastPower(__int64 radix,__int64 n,__int64 mod)//遞歸實(shí)現(xiàn)快速取模
{
if(n==1)
return radix%mod;
if(n==0)
return 1;
__int64 c=FastPower(radix,n>>1,mod);
return (1&n)==1?(radix*c*c)%mod:(c*c)%mod;
}
__int64 Gcd(__int64 a,__int64 b)//最大公因數(shù)
{
if(a==0)
return b;
return Gcd(b%a,a);
}
__int64 cmp(__int64 a,__int64 b){return a>b;}//排序的比較函數(shù)
void getPrimeFactor()//得到歐拉函數(shù)素因子分解式
{
__int64 temp=Q;
__int64 i,j;
//分解分母
for(i=0;Prime[i]*Prime[i]<=temp;i++)
{
if(temp%Prime[i]==0)
{
PrimeFactor[Cnt++]=Prime[i];
while(temp%Prime[i]==0)
{
temp/=Prime[i];
isCom[Prime[i]]++;
}
}
}
if(temp!=1)
{
PrimeFactor[Cnt++]=temp;
isCom[temp]++;
}
//分解分母的歐拉函數(shù)值
__int64 count=Cnt;
for(i=0;i<count;i++)
{
isCom[PrimeFactor[i]]--;
__int64 copy=PrimeFactor[i];
if(isCom[PrimeFactor[i]]==0)
PrimeFactor[i]=0;
copy--;
for(j=0;Prime[j]*Prime[j]<=copy;j++)
{
if(copy%Prime[j]==0)
{
if(isCom[Prime[j]]==0)
{
PrimeFactor[Cnt++]=Prime[j];
}
while(copy%Prime[j]==0)
{
copy/=Prime[j];
isCom[Prime[j]]++;
}
}
}
if(copy!=1)
{
if(isCom[copy]==0)
PrimeFactor[Cnt++]=copy;
isCom[copy]++;
}
}
//對(duì)因子排序，由大到小
sort(PrimeFactor,PrimeFactor+Cnt,cmp);
Cnt=0;
while(PrimeFactor[++Cnt]);
}
void solve(__int64 depth)//遞歸尋找因子，各個(gè)計(jì)算
{
if(depth==Cnt)
{
if(Factor<ans2)
{
if(FastPower(2,Factor,Q)==1)
ans2=Factor;
}
return ;
}
solve(depth+1);
for(__int64 i=1;i<=isCom[PrimeFactor[depth]];i++)
{
for(__int64 j=1;j<=i;j++)
Factor*=PrimeFactor[depth];
solve(depth+1);
for(__int64 k=1;k<=i;k++)
Factor/=PrimeFactor[depth];
}
}
int main()
{
getPrime();
int t=0;
while(scanf("%I64d/%I64d",&P,&Q)!=EOF)
{
//變量初始化
for(__int64 i=0;i<Cnt;i++)
isCom[PrimeFactor[i]]=0;
memset(PrimeFactor,0,sizeof(PrimeFactor));
ans2=INF;
ans1=1;
Cnt=0;
Factor=1;
cout<<"Case #"<<++t<<": ";
P%=Q;
Q/=Gcd(P,Q);
while(!(1&Q))
{
Q>>=1;
ans1++;
}
//特殊情況
if(P==0)
{
cout<<"1,1 "<<endl;
continue;
}
else if(Q==1)
{
printf("%I64d,1 \n",ans1);
continue;
}
getPrimeFactor();//得到因子分解
solve(0);//遞歸求解
printf("%I64d,%I64d \n",ans1,ans2);//結(jié)果
}
return 0;
}