题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=775
关于扩展欧几里得算法还是推一遍好啦;
有方程:a*x+b*y=d=gcd(a, b) --- 1式(只要a, b不全为0则此方程必有解,不过我不会证明,望大神路过时教一下);
又有gcd(a, b)=gcd(b, a%b); --- 2 式 (证明: http://www.cnblogs.com/geloutingyu/p/6209026.html)
将2式代入1式中得到:b*x1+(a%b)*y1=b*x1+(a-a/b*b)*y1=a*y1+b*(x1-a/b*y1);----3式
比较1式和3式,由恒等式定理可得:x=y1; y=x1-(a/b)*y1; 即上一层递归式中的y就是本层递归式中的x,上一层递归式中的y就是 x1-(a/b)*y1;
代码:
#include <bits/stdc++.h>
#define ll long long
using namespace std; int x, y; void exgcd(int a, int b)
{
if(!b) //***b==0结束递归条件
{
x=;
y=;
return;
}
exgcd(b, a%b);
int t=x;
x=y;
y=t-(a/b)*y;
} int main(void)
{
int a, b, d;
while(~scanf("%d%d", &a, &b)) //××本题中这里用cin 会超时,即便加了输入外挂也一样,并不懂why;
{
exgcd(a, b);
printf("%d %d\n", x, y);
}
return ;
}
当然上面的exgcd函数还可以写的简洁一些:
void exgcd(int a, int b, int& d, int& x, int& y){
if(!b){
x=, y=, d=a;
}else{
exgcd(b, a%b, d, y, x);
y-=x*(a/b);
}
}