原题链接：https://atcoder.jp/contests/abc340/tasks/abc340_f
Time Limit: 2 sec / Memory Limit: 1024 MB
Score: 525 points
问题陈述
给你整数 X 和 Y，它们至少满足 或者
中的一个。
请找出一对满足以下所有条件的整数 (A,B)。如果不存在这样的一对，请报告。
- −10^18≤A,B≤10^18
- 顶点位于 xy 平面上点 (0,0),(X,Y),(A,B) 的三角形的面积为 1.
Constraints
- −10^17≤X,Y≤10^17
- X and Y are integers.
输入输出描述：
Input
The input is given from Standard Input in the following format:
X Y
Output
If there is a pair of integers (A,B) that satisfies the conditions, print it in the following format:
A B
Otherwise, print -1.
Sample Input 1Copy
3 5
Sample Output 1Copy
1 1
The area of the triangle with vertices at points (0,0),(3,5),(1,1) is 1. Thus, (A,B)=(1,1) satisfies the conditions.
Sample Input 2Copy
-2 0
Sample Output 2Copy
0 1
Sample Input 3Copy
8752654402832944 -6857065241301125
Sample Output 3Copy
-1
解题思路：
这个题目需要知道裴蜀定理和拓展欧几里得算法，还需要知道一个不太常用的三角形计算面积的公式，裴蜀定理详情见下面链接百度百科
裴蜀定理（或贝祖定理）得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性不定方程（称为裴蜀等式）：若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。
它的一个重要推论是：a,b互质的充分必要条件是存在整数x,y使ax+by=1.
我们已知了俩个点和三角形的面积，让我们求是否存在第三个点(x,y)满足这三个点组成的三角形面积为1，x和y都是整数，现在题目告诉我们已知的俩个点中有一个点是(0,0)，那么此时就有一个三角形面积的计算公式是假设我们已知的俩个点分别是(0,0)，(x1,y1)，我们设我们要求的那个点为(a,b)，那么此时就有一个不太常用的三角形面积的计算公式s=1/2*abs(b*x1-a*y1)=1，那么就可以得到abs(b*x1-a*y1)=2，根据裴蜀定理可以知道一定存在b*x1+a*y1=gcd(x1,y1)，显然可以发现当gcd(x1,y1)>=3时一定无解，因为根据裴蜀定理gcd(x1,y1)已经是能有x1,y1凑出来的最小值了，最小值都大于2了，那么肯定凑不出2，否则说明gcd(x1,y1)等于1或者2，那么当gcd(x1,y1)=1时，只需要将求出的(a,b)乘以2即可，当gcd(x1,y1)=2时，此时求出的(a,b)就是答案，根据本题式子，我们将(y,-x)放入exgcd进行i计算。
时间复杂度：利用到了拓展欧几里得算法时间为O(log(min(x1,y1))。
空间复杂度：使用了常数个变量，空间复杂度为O(1)，如果考虑严谨一点，exgcd里面每次使用了一个变量记录返回值，那么空间复杂度可以看为O(log(min(x1,y1))。
cpp代码如下：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int n, m;
int a[N];
LL exgcd(LL a, LL b, LL &x, LL &y)
{
if (!b)
{
x = 1, y = 0;
return a;
}
LL d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
int main()
{
LL x, y, a, b;
cin >> x >> y;
LL g = exgcd(y, -x, a, b); //等式为|ay-bx|=2,所以将(y,-x)放入exgcd求解
if (abs(g) >= 3) //无解
{
cout << -1 << endl;
}
else
{
cout << a * 2 / g << ' ' << b * 2 / g << endl;
}
return 0;
}
