poj 3358 Period of an Infinite Binary Expansion

由乘2取整得到分数的小数位,可以找到规律!!!

例如:1/10,2/10,4/10,8/10,16/10,32/10,64/10……

取整后:1/10,2/10,4/10,8/10,6/10,2/10,4/10……

这样我们就发现规律了!!!

也就是对于p/q而言,要满足2^x=2^y mod q (gcd(p,q)==1);

化简:2^x*(2^(x-y)-1) = 0 mod q;

q里面2的倍数有多少个,就是最小的循环起始位置。

继而化简:2^(x-y) = 1 mod q' (q'除以2的倍数之后的值)

也就是求2^t = 1 mod q'

由欧拉定理知道:t=phi(q');但是这求出的t不一定是最小的,所以应该枚举t的约数,继而得到答案……

链接http://poj.org/problem?id=3358

 #include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<string>
using namespace std;
int prime[],m;
bool f[];
void init()
{
__int64 i,j;
m=;
for(i=;i<=;i++)
{
if(f[i]==)
{
prime[m++]=i;
for(j=i*i;j<=;j+=i)
f[j]=;
}
}
}
__int64 gcd(__int64 a,__int64 b)
{
__int64 t;
if(a<b) swap(a,b);
while(b)
{
t=a;
a=b;
b=t%b;
}
return a;
}
__int64 euler(__int64 n)
{
__int64 ans=;
int i;
for(i=;i<m&&prime[i]<=n;i++)
{
if(n%prime[i]==)
{
n/=prime[i];
ans*=prime[i]-;
while(n%prime[i]==)
{
ans*=prime[i];
n/=prime[i];
}
}
}
if(n!=)
ans*=n-;
return ans;
}
__int64 pows(__int64 a,int b,__int64 m)
{
__int64 ans=;
while(b)
{
if(b&)
ans=ans*a%m;
b>>=;
a=a*a%m;
}
return ans;
}
int main()
{
init();
__int64 a,b,q,g,mmin;
int i,j,p,k=;
while(scanf("%I64d/%I64d",&a,&b)!=EOF)
{
if(a==)
printf("Case #%d: %d,%I64d\n",++k,,);
g=gcd(b,a);
a=a/g;b=b/g;
i=;
while(b%==)
{
b/=;
i++;
}
q=euler(b);j=i;
mmin=q;
for(i=;i*i<=q;i++)
{
if(q%i==)
{
if(pows(,i,b)==)
{
mmin=i;
break;
}
p=q/i;
if(pows(,p,b)==&&p<mmin) mmin=p;
}
}
printf("Case #%d: %d,%I64d\n",++k,j,mmin);
}
return ;
}
上一篇:C++ Primer 学习笔记_63_重载运算符和转换 --转换和类类型【上】


下一篇:jquery实现点击上移到顶部功能(转)