首先我们知道:顶点为 \((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;
}
标签:ABC340F,int,dfrac,exgcd,abc340,long,ay,bx
From: https://www.cnblogs.com/Ww-Aster-H2/p/18014906