没有合适的资源?快使用搜索试试~ 我知道了~
ACM数论模板~。。。
需积分: 9 22 下载量 198 浏览量
2010-07-20
21:59:37
上传
评论
收藏 145KB DOC 举报
温馨提示
试读
16页
目录 1 一. 扩展的欧几里德和不定方程的解 2 二. 中国同余定理 3 三. 原根 5 四. 积性函数 6 五. 欧拉函数性质 7 六. 线性求1-max的欧拉函数值 9 七. 求单个欧拉函数,求最小的x(phi(n)%x==0),使得2^x =1(mod n) 10
资源推荐
资源详情
资源评论
一. 扩展的欧几里德和不定方程的解
解不定方程 ax + by = n 的步骤如下:
(1)计算 gcd(a, b). 若 gcd(a, b)不能整除 n,则方程无整数解;否则,在方程的两边同除以
gcd(a, b),得到新的不定方程 a'x + b'y = n',此时 gcd(a', b') = 1
(2)求出不定方程 a'x + b'y = 1 的一组整数解 x0, y0,则 n'x0,n'y0 是方程 a'x + b'y = n'的
一组整数解。
(3)根据扩展欧几里德定理,可得方程 a'x + b'y = n'的所有整数解为:
x = n'x0 + b't
y = n'y0 - a't
(t 为整数)
这也就是方程 ax + by = n 的所有整数解
利用扩展的欧几里德算法,计算(a, b)和满足 gcd = (a, b) = ax0 + by0 的 x0 和 y0,也就
是求出了满足 a'x0 + b'y0 = 1 的一组整数解。因此可得:
x = n/gcd * x0 + b/gcd * t
y = n/gcd * y0 - a/gcd * t
(t 是整数)
int extend_Euclid(int a, int b, int &x, int &y)
{
if (b == 0){
x = 1;
y = 0;
return a;
}
int gcd= extend_Euclid ( b, a % b, x, y );
int temp = x;
x = y;
y = temp - (a / b) * y;
return gcd;
}
2
二. 中国同余定理
Poj 2891
#include<stdio.h>
#include<iostream>
using namespace std;
__int64 GCD(__int64 i,__int64 j)
{
if(j==0)
return i;
else
return GCD(j,i%j);
}
__int64 extend_Euclid(__int64 a, __int64 b, __int64 &x, __int64 &y)
{
if (b == 0){
x = 1;
y = 0;
return a;
}
__int64 gcd= extend_Euclid ( b, a % b, x, y );
__int64 temp = x;
x = y;
y = temp - (a / b) * y;
return gcd;
}
//只有两个式子的中国同余定理,return z=a*xx+x=b*yy+y;
__int64 CRT_2(__int64 a,__int64 x,__int64 b,__int64 y)
{
__int64 xx,yy,gcd;
gcd=extend_Euclid(a,b,xx,yy);
__int64 c=y-x;
while(c<0)
c+=a;
if(c%gcd!=0)
return -1;
xx*=c/gcd;
yy*=c/gcd;
__int64 t=yy/(a/gcd);
while(yy-t*(a/gcd)>0)
3
t++;
while(yy-(t-1)*(a/gcd)<=0)
t--;
return (t*(a/gcd)-yy)*b+y;
}
//chinese remainder theorem
//crt[i][0]存的是除数,crt[i][1]存的是余数,0<=i<n,n>1,返回结果,-1 表示无解
__int64 CRT(__int64 crt[][2],int n)
{
__int64 m=crt[0][0]/GCD(crt[0][0],crt[1][0])*crt[1][0]; //最大公约数
__int64 ans=CRT_2(crt[0][0],crt[0][1],crt[1][0],crt[1][1])%m;
for(int i=2;i<n&&ans!=-1;i++){
ans=CRT_2(m,ans,crt[i][0],crt[i][1]);
m*=crt[i][0]/GCD(m,crt[i][0]);
ans%=m;
}
return ans;
}
int main(void)
{
int n;
__int64 a[10000][2];
while(scanf("%d",&n)==1){
for(int i=0;i<n;i++)
scanf("%I64d%I64d",&a[i][0],&a[i][1]);
if(n==1)
printf("%I64d\n",a[0][1]);
else
printf("%I64d\n",CRT(a,n));
}
return 0;
}
4
剩余15页未读,继续阅读
资源评论
wqOoops
- 粉丝: 78
- 资源: 28
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功