• 如果喜欢本站,您可以按CTRL+D收藏本站,方便下次访问。

  • 欢迎来自五湖四海的朋友,期待为您分享有价值的资源 :oops:

POJ 3358 Period of an Infinite Binary Expansion求有理数循环节长度

POJ解题 第四度 10年前 (2010-08-15) 34次浏览 0个评论 扫描二维码

file

给定有理数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;
}

本网站采用BY-NC-SA 4.0协议进行授权 | 转载请注明原文链接:https://www.disidu.com/post/1008.html
如果觉得本文对您有帮助或者您心情好~可以微信打赏支持一下本站:↓↓↓
喜欢 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址