ABC340-F S = 1
(Test/Manual/abc340_f.test.cpp)

• View this file on GitHub
• Last update: 2024-11-29 05:08:07+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
• Link: https://atcoder.jp/contests/abc340/submissions/60264792

三点 $(a, b), (x, y), (p, q)$ からなる三角形の面積は $\frac{1}{2}\text{abs}((x - a)(q - b) - (y - b)(p - a))$ である。

とくに、三点 $(0, 0), (x, y), (p, q)$ からなる三角形の面積は $\frac{1}{2}\text{abs}(xq - yp)$ である。

本問題は一次不定方程式のかたちをしているため、拡張ユークリッドの互除法で解ける。

Depends on

• 拡張ユークリッドの互除法 (Src/Number/ExtendGCD.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

/*
 * AtCoder Beginner Contest 340 - F S = 1
 * https://atcoder.jp/contests/abc340/submissions/60264792
 */

#include "../../Src/Number/ExtendGCD.hpp"

#include <cmath>
#include <iostream>

void solve() {
    long long X, Y;
    std::cin >> X >> Y;
    auto [A, B]{zawa::ExtendGCD(Y, -X)};
    long long gcd{std::abs(A*Y + B*(-X))};
    if (gcd == 1) {
        A *= 2;
        B *= 2;
    }
    if (gcd <= 2) {
        std::cout << A << ' ' << B << '\n';
    }
    else {
        std::cout << -1 << '\n';
    }
}

int main() {
#ifdef ATCODER
    solve();
#else
    std::cout << "Hello World\n";
#endif
}

#line 1 "Test/Manual/abc340_f.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

/*
 * AtCoder Beginner Contest 340 - F S = 1
 * https://atcoder.jp/contests/abc340/submissions/60264792
 */

#line 2 "Src/Number/ExtendGCD.hpp"

#include <utility>

namespace zawa {

template <class T>
std::pair<T, T> ExtendGCD(T a, T b) {
    if (a == 0) return { T{0}, 1 };
    if (b == 0) return { T{1}, 0 };
    T px{1}, py{0}, x{0}, y{1};
    while (a % b) {
        T d{a / b}, r{a % b};
        T nx{px - d*x}, ny{py - d*y};
        px = x;
        py = y;
        x = nx;
        y = ny;
        a = b;
        b = r;
    }
    return {x, y};
}

} // namespace zawa
#line 9 "Test/Manual/abc340_f.test.cpp"

#include <cmath>
#include <iostream>

void solve() {
    long long X, Y;
    std::cin >> X >> Y;
    auto [A, B]{zawa::ExtendGCD(Y, -X)};
    long long gcd{std::abs(A*Y + B*(-X))};
    if (gcd == 1) {
        A *= 2;
        B *= 2;
    }
    if (gcd <= 2) {
        std::cout << A << ' ' << B << '\n';
    }
    else {
        std::cout << -1 << '\n';
    }
}

int main() {
#ifdef ATCODER
    solve();
#else
    std::cout << "Hello World\n";
#endif
}

Back to top page