题意：给你一个分数，求它在二进制下的循环节的长度，还有第一个循环节从哪一位开始。
For example, x = 1/10 = 0.0001100110011(00110011)w and 0001100110011 is a preperiod and 00110011 is a period of 1/10.
思路一：
我们可以观察一下1/10这组数据，按照二进制转换法(乘二法)，我们可以得到：
1/10 2/10 4/10 8/10 16/10 32/10 ...
然后都分子都尽可能减去10，得到：
1/10 2/10 4/10 8/10 6/10 2/10 ...
这时候，发现出现了重复，那么这个重复就是我们要求的最小循环。
抽象出模型如下：对p/q
首先p'=p/gcd(p,q)
q'=q/gcd(p,q);然后我们就是求p'*2^i == p'*2^j (mod q') (“==”表示同余,i<j)
经过变换得到：
p'*2^i*(2^(j-i)-1) ==0 (mod q')
也就是 q' | p'*2^i*(2^(j-i)-1)
由于gcd(p',q')=1,
得到： q' | 2^i*(2^(j-i)-1)
因为2^(j-i)-1为奇数，所以q'有多少个2的幂，i就是多少，而且i就是循环开始位置的前一位。
那么令q''为q'除去2的幂之后的数
此时 q'' | 2^(j-i)-1
也就是求出x,使得 2^x ==1 (mod q'')
就是求p*(2^i) == p*(2^j) (mod q)，除过来就是2^(i-j)==1（mod q）
思路二：转自http://www.cnblogs.com/Konjakmoyu/p/5183339.html
实现方法：
方法一： 直接BSGS
求2^x==1（mod n），就先消因子，然后在BSGS求解。
过程中如果b%d！=0，那就说明在x>=T时无解。
方法二：欧拉定理
先消因子，则2与n互质。
求2^x==1(mod n)，根据欧拉定理2^phi(n)==1(%n)，然后找phi(n)的质因子k。
从小到大枚举质因子k，判断2^k==1(%n)则的得到答案。
代码
BSGS的：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std; typedef long long LL;
const LL N=;
LL pl,bl;
LL p[N];
bool vis[N];
struct node{
LL d,id;
}bit[N]; bool cmp(node x,node y){
if(x.d==y.d) return x.id<y.id;
return x.d<y.d;
} LL exgcd(LL a,LL b,LL &x,LL &y)
{
if(b==) {x=,y=;return a;}
LL tx,ty;
LL d=exgcd(b,a%b,tx,ty);
x=ty;y=tx-(a/b)*ty;
return d;
} LL find(LL x)
{
int l=,r=bl;
while(l<=r)
{
int mid=(l+r)>>;
if(bit[mid].d==x) return bit[mid].id;
if(bit[mid].d<x) l=mid+;
if(bit[mid].d>x) r=mid-;
}
return -;
} void exBSGS(LL b,LL &xx,LL &yy)
{
LL t,m,g,x,y,pm,am;
while(b%==) {b/=;xx++;}
t=;
for(int i=;i<=;i++)
{
if(t%b==) {yy=i;return ;}
t=t*%b;
}
m=(LL)(ceil((double)sqrt((double)b)));
pm=%b;bit[].d=%b;bit[].id=;
for(int i=;i<=m;i++)
{
bit[i].d=bit[i-].d*%b;
bit[i].id=i;
pm=pm*%b;
}
sort(bit+,bit++m,cmp);
bl=;
for(int i=;i<=m;i++)
{
if(bit[i].d!=bit[bl].d) bit[++bl]=bit[i];
}
exgcd(pm,b,x,y);
am=x%b+b;
t=%b;
for(int i=;i<=m;i++)
{
x=find(t);
if(x!=-) {yy=i*m+x;return ;}
t=t*am%b;
}
return ;
} int main()
{
freopen("a.in","r",stdin);
freopen("b.out","w",stdout);
LL T=,a,b;
char c;
while(scanf("%I64d%c%I64d",&a,&c,&b)!=EOF)
{
LL x,y;
LL g=exgcd(a,b,x,y);
a/=g,b/=g;
x=,y=-;
exBSGS(b,x,y);
printf("Case #%I64d: %I64d,%I64d \n",++T,x,y);
}
return ;
}
欧拉定理的：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;typedef long long LL;
const LL Max=(LL)1e6;
const LL N=Max+;
LL fl;
LL f[N];LL gcd(LL a,LL b)
{
if(b==) return a;
return gcd(b,a%b);
}bool cmp(int x,int y){return x<y;}LL eular(LL x)
{
LL ans=x;
for(int i=;i*i<=x;i++)
{
if(x%i==) ans/=i,ans=ans*(i-);
while(x%i==) x/=i;
}
if(x>) ans/=x,ans=ans*(x-);
return ans;
}LL quickpow(LL a,LL b,LL mod)
{
LL ans=%mod;
while(b)
{
if(b&) ans=ans*a%mod;
a=a*a%mod;
b>>=;
}
return ans;
}void solve(LL b,LL &xx,LL &yy)
{
LL k=,x=b,ans=x;
while(b%==) xx++,b/=;
LL phi=eular(b);
for(int i=;i*i<=phi;i++)
{
if(phi%i==) f[++fl]=i,f[++fl]=phi/i;
}
sort(f+,f++fl,cmp);
for(int i=;i<=fl;i++)
{
if(quickpow(,f[i],b)==) {yy=f[i];return ;}
}
}int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
LL T=,a,b;
char c;
while(scanf("%I64d%c%I64d",&a,&c,&b)!=EOF)
{
LL x=,y=;
LL g=gcd(a,b);
a/=g,b/=g;
solve(b,x,y);
printf("Case #%I64d: %I64d,%I64d \n",++T,x,y);
}
return ;
}
