转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents
by---cxlove
题目:http://poj.org/problem?id=3358
将一个分数化成小数,转化成二进制后寻找循环节
对于分数P/Q而言,首先化成最简,调整为P'=P/GCD(P,Q) Q'=Q/GCD(P,Q)
我们知道转化成二进制,其实就是不断乘2,如果大于1,则去掉1,当前位为1,否则为0.
表示成分数的时候便是P/Q,2*P/Q如果分子大于分母,则减掉,也相当于取余。
于是我们假设在第I位的时候开始循环,第J位出现重复。
而出现循环反正在分数上便是分母和分子都相同,由于在这里分母是不变的,只考虑分子
那么(P'*2^I)%Q'==(P'*2^J)%Q ;
一个同余式,作 些调整 P'*(2^J-2^I)==0(MOD Q') P'*2^I*(2^(J-I)-1)==0(MOD Q')
变成P'*2^I*(2^(J-I)-1)|Q’
其中P'与Q'互质。那么2^I*(2^(J-I)-1)|Q’
而(2^(J-I)-1是奇数,那么I的值便是Q'里面有多少个2^的幂,第一部分已经解决
假设Q'除掉2的幂之后为Q''
那么Q''|(2^(J-I)-1),由费马小定理或者欧拉定理可知
若A与P互质,则A^PHI(P) == 1 (MOD P)
所以2^X ==1 (mod Q'')必定存在解。
我们要求的是最小的解,则枚举PHI(Q'')的因子,从小开始判断
2^X==1(MOD Q'')
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define LL long long
#define N 1000000
using namespace std;
LL gcd(LL a,LL b){
return b==0?a:gcd(b,a%b);
}
LL get_eular(LL n){
LL ret=1;
for(LL i=2;i*i<=n;i++)
if(n%i==0){
ret*=i-1;
n/=i;
while(n%i==0){
n/=i;
ret*=i;
}
}
if(n>1)
ret*=n-1;
return ret;
}
LL PowMod(LL a,LL b,LL MOD){
LL ret=1;
while(b){
if(b&1)
ret=(ret*a)%MOD;
a=(a*a)%MOD;
b>>=1;
}
return ret;
}
LL fact[100000],cnt;
void get_fact(LL n){
cnt=0;
for(LL i=2;i*i<=n;i++)
if(n%i==0){
fact[cnt++]=i;
fact[cnt++]=n/i;
}
}
int main(){
LL p,q;
int cas=0;
while(scanf("%lld/%lld",&p,&q)!=EOF){
LL t=gcd(p,q);
p/=t;
q/=t;
int c=1;
while(!(q&1)){
q/=2;
c++;
}
LL phi=get_eular(q),ans;
get_fact(phi);
fact[cnt++]=phi;
sort(fact,fact+cnt);
for(int i=0;i<cnt;i++)
if(PowMod(2,fact[i],q)==1){
ans=fact[i];
break;
}
printf("Case #%d: %d,%lld\n",++cas,c,ans);
}
return 0;
}
分享到:
相关推荐
hdu 1695 GCD(欧拉函数+容斥原理).docx
(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数
很实用的算法讲解,hdu的lcy老师讲解,还不错!!
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
The least common multiple (LCM) of a set of positive integers is the smallest positive integer which is divisible by all the numbers in the set. For example, the LCM of 5, 7 and 15 is 105. Input Input...
算法-欧拉回路(HDU-1878)(包含源程序).rar
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码