扩展欧几里得算法 扩展欧几里得算法以O(log n)的时间求出方程
文章图片
的一组特解(
文章图片
),通解为
文章图片
(t为任意整数)。先假设? > ?。显然?? ≡ c ??? ? 与(?%?)? ≡ c ??? ? 有相同的解?0。所以?? + ?? = ?与?%? ? + ?? = ?所有整点的横坐标相同……总之我个人觉得原理搞懂了很难且用处不大,知道求
文章图片
的模板就行。
文章图片
该模板用于求方程
文章图片
的特解,返回值为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
分析+代码 由通解公式
文章图片
得知,|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
推荐阅读
- HDU 5528【2015长春现场赛 B】 Count a * b
- 类欧几里得算法|[类欧几里得算法 数论] BZOJ 2987 Earthquake
- [数论] Codeforces 819D R #421 D.Mister B and Astronomers & 516E R #292 E. Drazil and His Happy Friends
- 模板 poj2947 Widget Factory 高斯消元
- 【扩展欧几里得】练习题
- 扩展欧几里得【数论
- 数论|hdu 5322 Hope(分治+NTT)
- HDU 5528 Count a × b
- 线性同余方程组
- 数论|AtCoder Beginner Contest 156 C.Rally