首页 > 代码库 > poj3358：欧拉定理
poj3358：欧拉定理
又是一道用欧拉定理解的题。。嗯，关键还是要建好方程，注意一些化简技巧
题目大意：
给定一个由 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 10000long 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=2;i*i<=n;i++) { if(n%i==0) { res=res-res/i; while(n%i==0) { n/=i; } } } if(n>1) res=res-res/n; return res;}long long multi(long long a,long long b,long long m)//a*b%m{ long long res=0; while(b>0) { if(b&1) res=(res+a)%m; b>>=1; a=(a<<1)%m; } return res;}long long quickmod(long long a,long long b,long long m) //a^b%m{ long long res=1; while(b>0) { if(b&1) res=multi(res,a,m); b>>=1; a=multi(a,a,m); } return res;}int main(){ long long p,q,x,y; int cas=0; while(scanf("%I64d/%I64d",&p,&q)!=EOF) { if(p==0) { puts("1,1"); continue; } cas++; long long t=gcd(p,q); x=1; p/=t;q/=t; while(q%2==0) { q/=2;x++; } long long m=phi(q); y=m; for(long long i=2;i*i<=m;i++) { if(m%i==0) { while(m%i==0) m/=i; while(y%i==0) { y/=i; if(quickmod(2,y,q)!=1) { y*=i; break; } } } } printf("Case #%d: %I64d,%I64d\n",cas,x,y); } return 0;}
poj3358：欧拉定理
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。