AT_abc340_f [ABC340F] S = 1
首先我们知道：顶点为 \((0,0),(x,y),(a,b)\) 的三角形的面积为 \(\dfrac{|ay-bx|}{2}\)。因此，问题转化为：给定整数 \(x,y\)，求一个整数对 \((a,b)\) 使得
\(|ay-bx|=2\)。
令 \(d=\gcd(x,y)\)：
- 如果 \(d\ge3\)，则答案不存在，因为 \(|ay-bx|\) 始终是 \(d\) 的倍数。
- 如果 \(d=1,2\)，则可以使用扩展欧几里得算法获得解，相当于求解方程 \(|my-nx|=d\)。
将 \((y,-x,m,n)\) 作为 exgcd 的输入，可以得到一对 \((m,n)\) 满足 \(|my-nx|=d\)，由此可得 \(a=\dfrac{2m}{d},b=\dfrac{2n}{d}\)。
复杂度 \(O(\log\min(x,y))\)。本题有 spj。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int x,y;
int exgcd(int a,int b,int &x,int &y)
{
int d=a;
if(b==0)
{
x=1;
y=0;
}
else
{
d=exgcd(b,a%b,y,x);
y-=a/b*x;
}
return d;
}
signed main()
{
ios::sync_with_stdio(false);
cin>>x>>y;
int a,b,d=__gcd(abs(x),abs(y));
if(d>=3)
{
cout<<-1;
return 0;
}
exgcd(y,-x,a,b);
cout<<a*2/d<<' '<<b*2/d;
return 0;
}