题意
给定 ( X , Y ) (X,Y) (X,Y)，其中 X , Y X,Y X,Y 为整数。求整数 A , B A,B A,B 使得由 ( 0 , 0 ) , ( X , Y ) , ( A , B ) (0,0),(X,Y),(A,B) (0,0),(X,Y),(A,B) 三个点构成的三角形面积为 1 1 1。
思路
将 ( X , Y ) , ( A , B ) (X,Y),(A,B) (X,Y),(A,B) 看作 ( x 1 , y 1 ) , ( x 2 , y 2 ) (x_1,y_1),(x_2,y_2) (x1,y1),(x2,y2)，考虑 y = k x + b y = kx + b y=kx+b 过 ( x 1 , y 1 ) , ( x 2 , y 2 ) (x_1,y_1),(x_2,y_2) (x1,y1),(x2,y2)，根据求一次函数解析式得
{ k = y 2 − y 1 x 2 − x 1 b = x 2 y 1 − y 2 x 1 x 2 − x 1 \begin{cases}k = \dfrac{y_2 - y_1}{x_2 - x_1}\\ b = \dfrac{x_2y_1 - y_2x_1}{x_2 - x_1}\end{cases} ⎩ ⎨ ⎧k=x2−x1y2−y1b=x2−x1x2y1−y2x1
考虑函数与 x x x 轴交点，令交于 ( t , 0 ) (t,0) (t,0)，则 t k + b = 0 tk + b = 0 tk+b=0， t ( y 2 − y 1 ) x 2 − x 1 + x 2 y 1 − y 2 x 1 x 2 − x 1 = 0 \dfrac{t(y_2 - y_1)}{x_2 - x_1} + \dfrac{x_2y_1 - y_2x_1}{x_2 - x_1} = 0 x2−x1t(y2−y1)+x2−x1x2y1−y2x1=0
t ( y 2 − y 1 ) + ( x 2 y 1 − y 2 x 1 ) = 0 t(y_2 - y_1) + (x_2y_1 - y_2x_1) = 0 t(y2−y1)+(x2y1−y2x1)=0
解得
t = − ( x 2 y 1 − y 2 x 1 ) ( y 2 − y 1 ) t = -\dfrac{(x_2y_1 - y_2x_1)}{(y_2 - y_1)} t=−(y2−y1)(x2y1−y2x1)
1 = ∣ S ∣ = ∣ t × ( y 2 − y 1 ) 2 ∣ = ∣ − ( x 2 y 1 − y 2 x 1 ) 2 ∣ 1 = |S| = |\dfrac{t \times (y_2 - y_1)}{2}| = |\dfrac{-(x_2y_1 - y_2x_1)}{2}| 1=∣S∣=∣2t×(y2−y1)∣=∣2−(x2y1−y2x1)∣
因此 ∣ x 2 y 1 − y 2 x 1 ∣ = 2 |x_2y_1 - y_2x_1| = 2 ∣x2y1−y2x1∣=2，即 ∣ A Y − B X ∣ = 2 |AY - BX| = 2 ∣AY−BX∣=2，不妨令 A Y − B X = 2 AY - BX = 2 AY−BX=2，考虑 X , Y X,Y X,Y 已经给出，用 exgcd 解决即可。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int x,y;
int exgcd(int a,int b) {if(!b) {x = 1;y = 0;return a; }int d = exgcd(b,a % b);int t = x;x = y;y = t - (a / b) * y;return d;
}
signed main() {int a,b,c = 2;scanf("%lld %lld",&a,&b);swap(a,b);b = -b;int d = exgcd(a,b);if(c % d) {printf("-1\n");return 0;} x *= c / d,y *= c / d;printf("%lld %lld\n",x,y);return 0;
}
