题目描述：
题意：
就是给定一个a/b，求a/b的结果变成二进制之后的小数。这个小数后面会有一段循环节，只要求输出循环节开始循环的位置和循环长度。
分析：
这题我是这么想的，比如说样例中的1/5，我们可以像平时列竖式那样算，不过要先把a和b转成二进制，然后在二进制的条件下计算。
当余数重复的时候，答案的小数部分就开始出现循环节了。我们回想一下做竖式时的过程：我们是每次把在余数后面加一个0，然后除以b，而留下来余数继续这样做。当余数重复的时候开始出现循环节。我们每次在后面加一个0的过程，因为是在二进制下的，就相当于每次把余数乘2，再进行除法，得到新的余数。
开始时先把a/b化到最简，这是第一步。
假设刚开始我们用a/b得到的余数是k，后来我们每次乘以2，然后每次mod b得余数，什么时候余数重复了呢？
我们先假设2和b互质（即b是一个奇数），第x次操作的余数和第y次操作的余数相等，即：
k*2^x=k*2^y(mod b) --> 2^x=2^y(mod b) --> 2^(y-x)=1(mod b)
我们要求的是最小的y-x，假设2在mod b时的阶是m，那么m=y-x，这个时候小数循环节在第一位开始了。
如果2和b不互质呢？（即b是偶数）
解决方法跟前面的拓展BSGS的思想一样，消因子~~
#include<cstdio>
#include<cstring>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define Maxn 1000010
#define LL long long
char s[]; LL gcd(LL a,LL b)
{
if(b==) return a;
return gcd(b,a%b);
} LL eular(LL x)
{
LL ans=x;
for(LL i=;i*i<=x;i++)
{
if(x%i!=) continue;
ans=ans*(i-)/i;
while(x%i==) x/=i;
}
if(x>) ans=ans*(x-)/x;
return ans;
} LL qpow(LL a,LL b,LL p)
{
LL ans=%p;
while(b)
{
if(b&) ans=(ans*a)%p;
a=(a*a)%p;
b>>=;
}
return ans;
} int main()
{
LL p,q;
int kase=;
while(scanf("%s",s+)!=EOF)
{
LL l=strlen(s+),i,cnt=;
p=;q=;
for(i=;i<=l;i++)
{
if(s[i]=='/') break;
p=p*+s[i]-'';
}
for(i=i+;i<=l;i++)
q=q*+s[i]-'';
LL g;
while((g=gcd(p,q))!=) p/=g,q/=g;
while(q%==) q/=,cnt++;
LL phi=eular(q),ans=;
for(LL i=;i*i<=phi;i++)
{
if(phi%i==&&qpow(,i,q)==) {ans=i;break;}
if(phi%i==&&qpow(,phi/i,q)==) ans=phi/i;
}
printf("Case #%d: %lld,%lld \n",++kase,cnt+,ans);
}
return ;
}
poj3358
2016-02-05 16:54:56