生若有余

給定有理數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;
}