数论基础辗转相除扩展欧几里德

本文主要是介绍数论基础辗转相除扩展欧几里德，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

辗转相除：

辗转相除，又称为欧几里德算法，用于求解俩个数值的最大公约数，原理如下：

 gcd(a,b) = gcd(b,a%b) = gcd(a%b,(a%b)%b) ... = gcd(c,0) = c;

一般经过俩次的递归之后，第一个参数就小于原来的一半，所以不用但是栈溢出的情况。

int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);
}

求解n个数值的最小公倍数，即求解n个数值的最大公约数即可。lcm(a,b) = a*b / gcd(a,b);

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;int gcd(int a,int b){return b==0?a:gcd(b,a%b);   //辗转相除 gcd（a,b）=gcd(b,a%b) 结束条件是 gcd（a,0）=a
}
//两个数的最小公倍数 是两个数的乘积除以两个数的最大公约数
int lcm(int a,int b){int result = gcd(a,b);return (a*b)/(result);
}
int main()
{int n;int res;int m;while(scanf("%d",&n)!=EOF){res = 1;while(n--){scanf("%d",&m);res = lcm(res,m);}printf("%d\n",res);}return 0;
}

扩展欧几里德：

对应于ax+by = gcd(a,b) 存在着x,y使得成立，x,y不一定是正数。

推导：

ax+by = gcd(a,b);if b == 0a*x + 0*y = gcd(a,0) = a;=> x = 1; y = 0;if a*b != 0a*x1 + b*y1 = gcd(a,b) = b*x2 + (a%b)*y2a%b = a-a/b*ba*x1 + b*y1 = b*x2 +(a-[a/b]*b)*y2a*x1 + b*y1 = a*y2 + b*(x2-[a/b]*y2)==> x1 = y2y1 = x2-(a/b)*y2x1,y1是基于x2,y2的 递归总会出现b==0的时候

代码：

 int extgcd(int a,int b,int &x,int &y){if(b==0){x = 1;y =0;return a;}else{int res = extgcd(b,a%b,x,y);int tmp = x;x = y;y = tmp-(a/b)y;return res;}}

用扩展欧几里德可以判断 ax+by=c 是否存在着整数解

当ax+by=gcd(a,b)的成立且解为x,y 所以就是当c是gcd(a,b)的整数倍的时候，存在着解，解为xc/gcd(a,b),yc/gcd(a,b)

 bool linear_equation(int a,int b,int c,int &x,int &y){int d = extgcd(a,b,x,y);if(c%d)return false;int k = c/d;x *= k;y *= k;cout<<"x="<<x<<" "<<"y="<<y<<endl;return true;}

main()函数：

int main(){int a,b,c,x,y;cin>>a>>b>>c;int result = extgcd(a,b,x,y);cout<<result<<endl;bool flag =linear_equation(a,b,c,x,y);if(flag)cout<<"answer exit"<<endl;elsecout<<"No answer"<<endl;
}

样例： 模线性方程

ax和b(mod)n同余也就是a%n = b%n 所以存在着n使得 a-b = ny 原来方程变为ax - b = ny

可得：ax-ny = b; 当b=1的时候，也即gcd(a,n)=1,1/gcd(a,n)有解说明a,n必须互素也即gcd(a,n)=1成立的时候存在着唯一解。

模运算公式：

（a+b）mod n = ((a mod n)+(b mod n)) mod n

（a-b）mod n = ((a mod n)-(b mod n)+n) mod n

（a*b）mod n = ((a mod n)*(b mod n)) mod n

大整数取模

根据上面的性质：1234 =( ((1*10+2)*10)+3)*10+4.......大数表示方法 mod m；

代码：

int main(){int m;int ans = 0;scanf("%s%d",n,&m);int len = strlen(n);for(int i=0;i<len;i++)ans = (int)(((long long)ans*10+n[i])%m);printf("%d\n",ans);return 0;
}

这篇关于数论基础辗转相除扩展欧几里德的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！