verify/aoj/aoj_ntl_1_e.test.cpp

• View this file on GitHub
• Last update: 2024-06-26 02:37:52+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/NTL_1_E

Depends on

• 拡張ユークリッドの互除法 (math/ext_gcd.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/NTL_1_E"

#include <bits/stdc++.h>
using namespace std;

#include "../../math/ext_gcd.hpp"

int main() {
    int a, b;
    cin >> a >> b;
    auto [d, x, y] = ext_gcd(a, b);
    cout << x << " " << y << endl;

    return 0;
}

#line 1 "verify/aoj/aoj_ntl_1_e.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/NTL_1_E"

#include <bits/stdc++.h>
using namespace std;

#line 1 "math/ext_gcd.hpp"
tuple<long long, long long, long long> ext_gcd(long long a, long long b) {
    if(b == 0) return {a, 1, 0};
    auto [d, y, x] = ext_gcd(b, a % b);
    y -= a / b * x;
    return {d, x, y};
}
#line 7 "verify/aoj/aoj_ntl_1_e.test.cpp"

int main() {
    int a, b;
    cin >> a >> b;
    auto [d, x, y] = ext_gcd(a, b);
    cout << x << " " << y << endl;

    return 0;
}

Back to top page