扩展欧几里得算法——例题3( 最大公约数问题1)

扩展欧几里得算法 扩展欧几里得算法以O(log n)的时间求出方程 扩展欧几里得算法——例题3( 最大公约数问题1)
文章图片
的一组特解(扩展欧几里得算法——例题3( 最大公约数问题1)
文章图片
),通解为扩展欧几里得算法——例题3( 最大公约数问题1)
文章图片
(t为任意整数)。先假设? > ?。显然?? ≡ c ??? ? 与(?%?)? ≡ c ??? ? 有相同的解?0。所以?? + ?? = ?与?%? ? + ?? = ?所有整点的横坐标相同……总之我个人觉得原理搞懂了很难且用处不大,知道求 扩展欧几里得算法——例题3( 最大公约数问题1)
文章图片
的模板就行。
扩展欧几里得算法——例题3( 最大公约数问题1)
文章图片
该模板用于求方程扩展欧几里得算法——例题3( 最大公约数问题1)
文章图片
的特解,返回值为gcd(a,b),x、y将保存一组特解。
最大公约数问题1 题目描述 输入正整数A和B,求一组X, Y,使得方程:AX+BY=GCD(A, B)
输出|X| + |Y| 最小的一组X和Y
输入 第1行:1个整数T,表示测试数据的组数 (1 <= T <= 100)
【扩展欧几里得算法——例题3( 最大公约数问题1)】接下来T行,每行2个整数,表示A和B (1 <= A, B <= 1000)
输出 输出T行,每行2个整数,表示X和Y
样例输入

1 14 8

样例输出
-1 2

分析+代码 由通解公式扩展欧几里得算法——例题3( 最大公约数问题1)
文章图片
得知,|X|+|Y| 最小的就是exgcd()求出的特解!所以直接套用扩展欧几里得算法就行。
#include #include #include #include using namespace std; int read() { int f = 1,x = 0; char s = getchar(); while(s < '0' || s > '9') {if(s == '-')f = -1; s = getchar(); } while(s >= '0' && s <= '9') {x = x * 10 + s - '0'; s = getchar(); } return x * f; } bool f[2005]; int p[2005]; int n,m,i,j,k,s,o,num,num1; int exgcd(int a,int b,int &x,int &y) { if(!b) { x = 1,y = 0; return a; } else { int r = exgcd(b,a % b,y,x); //很混乱,所以要好好记 y -= x * (a / b); return r; } } int main() { n = read(); while(n --) { s = read(); o = read(); exgcd(s,o,i,j); printf("%d %d\n",i,j); } return 0; }

下一篇:扩展欧几里得算法——例题4: 最大公约数问题2

    推荐阅读