poj3358：欧拉定理

又是一道用欧拉定理解的题。。嗯，关键还是要建好方程，注意一些化简技巧

题目大意：

给定一个由 p / q 生成的循环小数，求此循环小数在二进制表示下的最小循环节以及不是循环节的前缀

思路：

小数化为二进制，应该乘2取余， 设从小数的第x位开始有长度为y的循环节，

先把 p/q 化为最简分数，此时p，q互质

则应该满足 同余方程 p*2^x=p*2^(x+y) mod q

整理一下可得  q | p*2^x*(2^y - 1) 由于 p，q互质，则q | 2^x*(2^y - 1)

此时 由于 2^y-1是奇数，则有次整除式可知 q中2的因数个数即为 x，因此可以处理 q 得到 x，同时将q变为 q/(2^x);

最终得到同余方程   2^y=1 (mod q)

利用欧拉定理解此同余方程即可

代码如下

#include <iostream>
#include <stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<ctype.h>
using namespace std;
#define MAXN 10000
long long gcd(long long a,long long b)
{
    return b?gcd(b,a%b):a;
}
long long phi(long long n)
{
    long long res=n;
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            res=res-res/i;
            while(n%i==0)
            {
                n/=i;
            }
        }
    }
    if(n>1)
        res=res-res/n;
    return res;
}
long long multi(long long a,long long b,long long m)//a*b%m
{
    long long res=0;
    while(b>0)
    {
        if(b&1)
            res=(res+a)%m;
        b>>=1;
        a=(a<<1)%m;
    }
    return res;
}
long long quickmod(long long a,long long b,long long m) //a^b%m
{
    long long res=1;
    while(b>0)
    {
        if(b&1)
            res=multi(res,a,m);
        b>>=1;
        a=multi(a,a,m);
    }
    return res;
}

int main()
{

    long long p,q,x,y;
    int cas=0;
    while(scanf("%I64d/%I64d",&p,&q)!=EOF)
    {
        if(p==0)
        {
            puts("1,1");
            continue;
        }
        cas++;
        long long t=gcd(p,q);
        x=1;
        p/=t;q/=t;
        while(q%2==0)
        {
            q/=2;x++;
        }
        long long m=phi(q);
        y=m;
        for(long long i=2;i*i<=m;i++)
        {
            if(m%i==0)
            {
                while(m%i==0)
                    m/=i;
                while(y%i==0)
                {
                    y/=i;
                    if(quickmod(2,y,q)!=1)
                    {
                        y*=i;
                        break;
                    }
                }
            }
        }
        printf("Case #%d: %I64d,%I64d
",cas,x,y);
    }


    return 0;
}