给定有理数P/Q，求它的二进制小数的循环节长度。
先把这个分数化为既约分数，则循环节开始的位置M是使满足2^M | Q的最大M。令Q1=Q/2^M,则循环节的长度就是求最小的N使2^N模Q1为1。这个问题好像没有有效的解法（关于Q1的位数为多项式级别）。由于2和Q1互素，可以用欧拉定理来解。即2^phi（Q1）对Q1同余1。所求的N一定是phi（Q1）的一个因子，先分解Q1，再分解phi（Q1），递归枚举phi（Q1）的所有因子，快速取幂算之，找到最小的满足要求的phi（Q1）的因子即为所求。
只是异常繁琐，而且分解因子要生成素数表，对时空要求都较高，不知有什么更佳的办法。
/**//*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;//输出结果
__int64 Factor;//递归寻找因子的时候用到
const __int64 INF=1000000000000000;
const __int64 MAXN=400000;
__int64 isCom[MAXN];//
__int64 Prime[MAXN];//素数表
void getPrime()//线性生成400000以内的素数
{
__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)//递归实现快速取模
{
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)//最大公因数
{
if(a==0)
return b;
return Gcd(b%a,a);
}
__int64 cmp(__int64 a,__int64 b){return a>b;}//排序的比较函数
void getPrimeFactor()//得到欧拉函数素因子分解式
{
__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]++;
}
//分解分母的欧拉函数值
__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]++;
}
}
//对因子排序，由大到小
sort(PrimeFactor,PrimeFactor+Cnt,cmp);
Cnt=0;
while(PrimeFactor[++Cnt]);
}
void solve(__int64 depth)//递归寻找因子，各个计算
{
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);//结果
}
return 0;
}