ABC340 F - F - S = 1

2024-02-12

공식 에디토리얼

문제 링크
https://atcoder.jp/contests/abc340/tasks/abc340_f

원문 링크
https://atcoder.jp/contests/abc340/editorial/9250

우선 중요한 사실은 \((0,0),(X,Y),(A,B)\)를 세 점으로 하는 삼각형의 면적은 \(\frac{\vert AY - BX \vert}{2}\)입니다.
따라서 이 문제는 \(X, Y\)가 주어졌을 때

\[\vert AY - BX \vert = 2\]

를 만족하는 정수쌍 \((A,B)\)를 찾는 문제로 바꿔 말할 수 있습니다.

이 문제의 풀이법을 설명하겠습니다. \(g = \mathrm{gcd}(X, Y)\)라 하겠습니다. (주의: \(\mathrm{gcd}\)는 \(\vert a \vert\)와 \(\vert b \vert\)의 최대공약수로 정의하겠습니다.)
우선 \(g\)가 \(3\)이상일 때는 확장 유클리드 호제법이라는 알고리즘을 사용해 항상 해를 구하는 걷이 가능합니다.
확장 유클리드 호제법은 정수쌍 \((a, b)\)를 입력했을 때 다음 순서에 따라 \(ax + by = \pm \mathrm{gcd}(a, b)\)가 되는 정수쌍 \((x, y)\)를 \(O(\log \min(\vert a \vert, \vert b \vert))\) 시간에 계산하는 알고리즘입니다. (여기서 정수쌍 \((x, y)\)는 \(\max(\vert x \vert, \vert y \vert) \leq \max(\vert a \vert, \vert b \vert)\)를 만족하는 정수임이 보장됩니다.)

//확장 유클리드 호제법 구현의 예시
pair<long long, long long> extgcd(long long a, long long b) {
    if (b == 0) return make_pair(1, 0);
    long long x, y;
    tie(y, x) = extgcd(b, a % b);
    y -= a / b * x;
    return make_pair(x, y);
}

확장 유클리드 호제법에 \((Y, -X)\)를 입력하는 것으로 나온 반환값을 \((c, d)\)랄 할 때,

\[cY - dX = \pm g\]

이며, \(\vert c \vert, \vert d \vert \leq 10^{17}\)인 쌍을 찾을 수 있습니다. 구하는 값은 \(AY - BX = \pm 2\)를 만족하는 \((A, B)\)의 쌍이고, 이것은 \((c, d)\)를 \(\frac{2}{g}\)배 하는 것으로 구할 수 있습니다. 이 \((A, B)\)는 \(\vert A \vert, \vert B \vert \leq 10^{18}\)이라는 제약을 만족합니다.

이상의 방법으로 이 문제를 풀 수 있습니다. 시간복잡도는 \(O(\log \min(X, Y))\) 정도로 충분히 빠릅니다.

뭐 쓰는진 알았는데

예전에 확장 유클리드 호제법을 공부했어서 쓴다는 것쯤은 보고 파악했다.
하지만 E번 디버깅에 힘을 너무 쏟은 나머지…

다음부터는 빨리 푸는것도 염두에 두고 해야겠다.