可以做文档赚钱的网站,做哪个视频网站赚钱的,photoshop网站模板,如何让搜素引擎不收录自己的网站欧几里得算法#xff1a;
int gcd(int x,int y){if(y) return gcd(y,x%y);return x;
}扩展欧几里得算法#xff1a;
先说一个整体思路#xff1a; 先求AxBygcd(A,B);的一个解x#xff0c;y 然后我们可以求他的通解 然后求AxByC的通解
我们先看看怎么求AxBygcd(A,B);的一…欧几里得算法
int gcd(int x,int y){if(y) return gcd(y,x%y);return x;
}扩展欧几里得算法
先说一个整体思路 先求AxBygcd(A,B);的一个解xy 然后我们可以求他的通解 然后求AxByC的通解
我们先看看怎么求AxBygcd(A,B);的一个解xy 设 ab。 1显然当 b0gcdaba。此时 x1y0 2ab0 时 设 ax1 by1 gcd(a,b); bx2 (a mod b)y2 gcd(b,a mod b); 根据朴素的欧几里德原理有 gcd(a,b) gcd(b,a mod b); 则:ax1 by1 bx2 (a mod b)y2; 即:ax1 by1 bx2 (a - [a / b] * b)y2ay2 bx2- [a / b] * by2; 也就是ax1 by1 ay2 b(x2- [a / b] *y2);
根据恒等定理得x1y2; y1x2- [a / b] *y2; 这样我们就得到了求解 x1,y1 的方法x1y1 的值基于 x2y2. 上面的思想是以递归定义的因为 gcd 不断的递归求解一定会有个时候 b0所以递归可以结束。
void Ex_gcd(int a, int b, int x, int y)
{if(b 0)//递归出口{x 1;y 0;return;}int x1, y1;Ex_gcd(b, a%b, x1, y1);x y1;y x1-(a/b)*y1;
}
上面已经列出找一个整数解的方法我们接下来找通解
取另外一组解x2y2 则ax1by1ax2by2gcd(a,b) 变形得a(x1-x2)b(y1-y2) 假设gcda,b)g 方程左右两边同时除以g a’(x1-x2)b’(y2-y1),a’a/g,b’b/g 此时a’和b’互为素数 因此x1-x2一定是b’的整数倍,设为kb’ 因此若方程一组整数解为x0y0 他的任意整数解都可写成 x0kb’,y0-ka’ a’a/gcd(a,b) b’b/gcd(a,b)
结论在找到AxBy Gcd(A, B)的一组解x0,y0后AxBy Gcd(A, B)的其他整数解满足 x x0 B/Gcd(A, B) * t y y0 - A/Gcd(A, B) * t(其中t为任意整数)
明白了原始的AxBygcd(A,B)情况我们可以扩展到一般的情况即
AxByC
对于AxByc的整数解只需将AxBy Gcd(A, B)的每个解乘上 C/Gcd(A, B) 即可 但是所得解并不是该方程的所有解找其所有解的方法如下 在找到AxBy Gcd(A, B)的一组解x0,y0后可以 得到AxBy C的一组解x1 x0*(C/Gcd(A,B)),y1 y0*(C/Gcd(A,B))AxBy C的其他整数解满足 x x1 B/Gcd(A, B) * t y y1 - A/Gcd(A, B) * t(其中t为任意整数) y就是AxByC的所有整数解。
练习题目
Now tell you two nonnegative integer a and b. Find the nonnegative integer X and integer Y to satisfy Xa Yb 1. If no such answer print “sorry” instead. Input The input contains multiple test cases. Each case two nonnegative integer a,b (0 a, b 2^31) Output output nonnegative integer X and integer Y, if there are more answers than the X smaller one will be choosed. If no answer put “sorry” instead. Sample Input 77 51 10 44 34 79 Sample Output 2 -3 sorry 7 -3
分析与解答
代码参考只有这个代码才是这个算法的真谛
#include iostream
#include cstdio
#include cmath
#include cstring
#include string
#include cstdlib
using namespace std;long long gcd(long long a,long long b){if(!b) return a;return gcd(b,a%b);
}void exgcd(long long a,long long x,long long b,long long y){if(!b){x1;y0;}else{exgcd(b,y,a%b,x);y-x*(a/b);}
}
int main(){long long t,A,B,x,y;while(cinAB){if(gcd(A,B)!1)coutsorryendl;else{exgcd(A,x,B,y);//已经得到了一个特解xywhile(x0) {xB;y-A;}//找最小的正整数解coutx yendl;}}return 0;
}
