欧几里得算法(Euclid)
欧几里得重要结论:
1:gcd(a,b) = gcd(b,a %b)
2:gcd(a,0) = a
背景:
欧几里德算法又称辗转相除法,用于计算两个正整数a,b的最大公约数。
——百度百科
代码
int n_gcd(int a,int b) // 求a,b最大公约数 { if(b == 0) return a; return n_gcd(b , a%b); // 欧几里德定理gcd(a,b) == gcd(b , a%b) }
利用欧几里德算法求2个数的最小公倍数
代码
#include#include #include using namespace std; int gcd(int a, int b) // 欧几里德算法 { if(b == 0) return a; return gcd(b, a % b); } int main() { int num1, num2, sum, ans, res; while(~scanf("%d %d", &num1, &num2)) { sum = num1 * num2; res = gcd(num1, num2); ans = sum / res; // 最小公倍数为2个数的积除以2个数的最大公约数 cout << ans << endl; } }
拓展欧几里得(Extend- Euclid)
背景:
扩展欧几里德算法是用来在已知a, b求解一组x,y [x,y都是整数],使它们满足贝祖等式: ax+by = gcd(a, b) =d(解一定存在,根据数论中的相关定理)。
扩展欧几里德常用在求解模线性方程及方程组中。
——百度百科
代码
int e_gcd(int a,int b,int &x,int &y) // 扩展欧几里德定理 { int ans,temp; if(b == 0) { x = 1; y = 0; return a; } ans = e_gcd(b,a%b,x,y); temp = x; x = y; y = temp - a/b*y; return ans; }
乘法逆元
代码
int cal(int a,int m) // 求a对m的乘法逆元 { /* a * x = 1 (mod m),x是a关于m的乘法逆元 等价于:a * x + m * y = 1 */ int x,y,gcd,ans; gcd = e_gcd(a,m,x,y); if(1 % gcd != 0) return -1; x *= 1 / gcd; m = abs(m); ans = x % m; if(ans <= 0) ans += m; return ans; }
http://blog.csdn.net/ACMore_Xiong/article/details/47694909
http://blog.csdn.net/zhjchengfeng5/article/details/7786595
http://blog.csdn.net/zhjchengfeng5/article/details/7786595
Comments | NOTHING