本文主要是介绍I - 扩展欧几里得！ CodeForces - 7C，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
A line on the plane is described by an equation Ax + By + C = 0. You are to find any point on this line, whose coordinates are integer numbers from - 5·1018 to 5·1018 inclusive, or to find out that such points do not exist.
Input
The first line contains three integers A, B and C ( - 2·109 ≤ A, B, C ≤ 2·109) — corresponding coefficients of the line equation. It is guaranteed that A2 + B2 > 0.
Output
If the required point exists, output its coordinates, otherwise output -1.
Examples
Input
2 5 3
Output
6 -3题目意思是给出二元一次方程的A*X+B*Y+C=0 给出A，B，C求一组合适的值是方程成立。
扩展欧几里得的推倒：
我们知道 gcd(a,b)=gcd(b,a%b);
则 a*x+b*y=gcd(a,b) 和 b*x+(a%b)*y=gcd(b,a%b) 是相等的。
然后 就有 a*x+b*y= a*x1+(a%b)*y1
设k=a/b有 a*x+b*y= b*x1+(a-k*b)*y1
a*x+b*y=b*x1+(a-(a/b)*b)*y1;
a*x+b*y=b*x1+a*y1-(a/b)*b*y1;
a*x+b*y=a*y1+b*(x1-(a/b)*y1);
所以得到 a*x=a*y1 --> x=y1;
b*y=b*(x1-(a/b)*y1) --> y=x1-(a/b)*y1;
所以扩展欧几里得的算法实现是
int gcd(int a,int b,int &x,int &y )
{int temp=a;if(b==0) //递推返回条件当b==0时;{x=1; //最后返回的条件是x=1，y=1;y=0;}else{temp=gcd(b,a%b,y,x); //辗转相除求最大公约数 b,a%b,就是交换a,b,的位置；y-=(a/b)*x; //公式推导出 x=y; y=x-(a/b)*y;// 前面的已将 x，y,交换位置所以后面的写法}return temp;
}
在本题中需要化成 a*x+b*y=gcd(a,b);的形式；
所以要同时除以 -C/gcd(A,B);
最后算结果时要乘上这个些才是这题的结果
完整代码如下；
#include<stdio.h>
long long int gcd(long long int a,long long int b,long long int &x,long long int &y )
{long long int temp=a;if(b==0) //递推返回条件当b==0时;{x=1; //最后返回的条件是x=1，y=1;y=0;}else{temp=gcd(b,a%b,y,x); //辗转相除求最大公约数 b,a%b,就是交换a,b,的位置；y-=(a/b)*x; //公式推导出 x=y; y=x-(a/b)*y;// 前面的已将 x，y,交换位置所以后面的写法}return temp;
}
int main()
{long long int a,b,c;while(~scanf("%lld%lld%lld",&a,&b,&c)){long long int x,y; //X,Y 最后结果是x=1 ,y=0;long long int r=gcd(a,b,x,y); //x=-x*c/r; //因为化成 ax+by=gcd(a,b);所以最后的结果要乘上 c/gcd(a,b);y=-y*c/r;if(c%r==0) //当gcd(a,b)==1 时才会有解， 这是ax+by=c有解的充要条件，既c% gcd(a,b)==0;printf("%lld %lld\n",x,y);elseprintf("-1\n");}return 0;
}
这篇关于I - 扩展欧几里得！ CodeForces - 7C的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
