又是一道用欧拉定理解的题。。嗯，关键还是要建好方程，注意一些化简技巧
题目大意：
给定一个由 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=;i*i<=n;i++)
{
if(n%i==)
{
res=res-res/i;
while(n%i==)
{
n/=i;
}
}
}
if(n>)
res=res-res/n;
return res;
}
long long multi(long long a,long long b,long long m)//a*b%m
{
long long res=;
while(b>)
{
if(b&)
res=(res+a)%m;
b>>=;
a=(a<<)%m;
}
return res;
}
long long quickmod(long long a,long long b,long long m) //a^b%m
{
long long res=;
while(b>)
{
if(b&)
res=multi(res,a,m);
b>>=;
a=multi(a,a,m);
}
return res;
} int main()
{ long long p,q,x,y;
int cas=;
while(scanf("%I64d/%I64d",&p,&q)!=EOF)
{
if(p==)
{
puts("1,1");
continue;
}
cas++;
long long t=gcd(p,q);
x=;
p/=t;q/=t;
while(q%==)
{
q/=;x++;
}
long long m=phi(q);
y=m;
for(long long i=;i*i<=m;i++)
{
if(m%i==)
{
while(m%i==)
m/=i;
while(y%i==)
{
y/=i;
if(quickmod(,y,q)!=)
{
y*=i;
break;
}
}
}
}
printf("Case #%d: %I64d,%I64d\n",cas,x,y);
} return ;
}