codeforces 7C 【扩展欧几里得算法】

2023-03-30

机器学习 amp ML.NET C# C Sharp line ll

B- 楼下水题TimeLimit:1000MS     MemoryLimit:262144KB     64bitIOFormat:%I64d&%I64uSubmit S

B - 楼下水题

Time Limit:1000MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64u

Submit Status Practice CodeForces 7C

Description

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·10¹⁸ to 5·10¹⁸ inclusive, or to find out that such points do not exist.

Input

The first line contains three integers A, B and C ( - 2·10⁹ ≤ A, B, C ≤ 2·10⁹) — corresponding coefficients of the line equation. It is guaranteed that A² + B² > 0.

Output

If the required point exists, output its coordinates, otherwise output -1.

Sample Input

Input

2 5 3

Output

6 -3

思路：

这道题是扩展欧几里得算法模板题，就是在最后求出x,y之后，还要将x,y带入到原方程里面，求出方程的结果，然后

用c再确定x,y的具体的值！

代码：


#include <stdio.h>
#include <string.h>
#include <algorithm>
typedef long long ll;
using namespace std;
ll a,b,c;
void gcd(ll a,ll b,ll& d,ll& x,ll& y)
{
if(!b)
{
d=a;
x=1;
y=0;
}
else
{
gcd(b,a%b,d,y,x);
y-=x*(a/b);
}
}
int main()
{
while(scanf("%lld%lld%lld",&a,&b,&c)!=EOF)
{
ll d,x,y;
gcd(a,b,d,x,y);
ll sum=a*x+b*y;
if(-c%sum!=0)
{
printf("-1\n");
}
else
{
ll k=-c/sum;
printf("%lld %lld\n",k*x,k*y);
}
}
return 0;
}