test/math/modint2.test.cpp

• View this file on GitHub
• Last update: 2025-10-26 10:54:48+08:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_E

Depends on

• src/math/modint.hpp

Code

// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_E
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
using namespace std;
using ll = long long;
using ull = unsigned long long;

#include "../../src/math/modint.hpp"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  ll a, b, x, y;
  cin >> a >> b;
  mint::exgcd(a, b, x, y);
  cout << x << " " << y << "\n";
  return 0;
}

#line 1 "test/math/modint2.test.cpp"
// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_E
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
using namespace std;
using ll = long long;
using ull = unsigned long long;

#line 1 "src/math/modint.hpp"
template <unsigned MOD>
struct ModInt {
  unsigned data;
  ModInt(ll v = 0) : data(norm(v % MOD)) {}
  ModInt operator-() const { return MOD - data; }
  ModInt& operator+=(ModInt rhs) { return data = norm(data + rhs.data), *this; }
  ModInt& operator-=(ModInt rhs) { return data = norm(data - rhs.data), *this; }
  ModInt& operator*=(ModInt rhs) {
    return data = ull(data) * rhs.data % MOD, *this;
  }
  ModInt& operator/=(ModInt rhs) {
    return data = ull(data) * rhs.inv() % MOD, *this;
  }
  friend ModInt operator+(ModInt lhs, ModInt rhs) { return lhs += rhs; }
  friend ModInt operator-(ModInt lhs, ModInt rhs) { return lhs -= rhs; }
  friend ModInt operator*(ModInt lhs, ModInt rhs) { return lhs *= rhs; }
  friend ModInt operator/(ModInt lhs, ModInt rhs) { return lhs /= rhs; }
  unsigned inv() const {
    ll x, y;  // Inverse does not exist if gcd(data, MOD) != 1.
    assert(exgcd(data, MOD, x, y) == 1);
    return norm(x);
  }
  ModInt pow(ull n) const { return pow_mod(data, n, MOD); }
  static ll exgcd(ll a, ll b, ll& x, ll& y) {
    x = 1, y = 0;
    ll x1 = 0, y1 = 1;
    while (b) {
      ll q = a / b;
      swap(a -= q * b, b);
      swap(x -= q * x1, x1);
      swap(y -= q * y1, y1);
    }
    return a;
  }
  static unsigned pow_mod(unsigned a, ull n, unsigned p) {
    unsigned ret = 1;
    for (; n; n /= 2) {
      if (n & 1) ret = ull(ret) * a % p;
      a = ull(a) * a % p;
    }
    return ret;
  }

 private:
  static unsigned norm(unsigned x) {
    if ((x >> (8 * sizeof(unsigned) - 1)) & 1) x += MOD;
    return x >= MOD ? x -= MOD : x;
  }
};
constexpr unsigned MOD = 998244353;
using mint = ModInt<MOD>;
#line 9 "test/math/modint2.test.cpp"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  ll a, b, x, y;
  cin >> a >> b;
  mint::exgcd(a, b, x, y);
  cout << x << " " << y << "\n";
  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	5 ms	4 MB
g++	00_sample_01.in	AC	4 ms	4 MB
g++	01_small_00.in	AC	4 ms	4 MB
g++	01_small_01.in	AC	4 ms	4 MB
g++	01_small_02.in	AC	4 ms	4 MB
g++	01_small_03.in	AC	4 ms	4 MB
g++	01_small_04.in	AC	4 ms	4 MB
g++	01_small_05.in	AC	4 ms	4 MB
g++	02_critical_00.in	AC	4 ms	4 MB
g++	02_critical_01.in	AC	4 ms	4 MB
g++	02_critical_02.in	AC	4 ms	4 MB
g++	02_critical_03.in	AC	4 ms	4 MB
g++	03_large_00.in	AC	4 ms	4 MB
g++	03_large_01.in	AC	4 ms	4 MB
g++	03_large_02.in	AC	4 ms	4 MB
g++	03_large_03.in	AC	4 ms	4 MB
g++	03_large_04.in	AC	4 ms	4 MB
g++	03_large_05.in	AC	4 ms	4 MB
g++	03_large_06.in	AC	4 ms	4 MB
g++	03_large_07.in	AC	4 ms	4 MB
g++	03_large_08.in	AC	4 ms	4 MB
g++	03_large_09.in	AC	4 ms	4 MB
g++	04_corner_00.in	AC	4 ms	4 MB
g++	04_corner_01.in	AC	4 ms	4 MB
g++	04_corner_02.in	AC	4 ms	4 MB
g++	04_corner_03.in	AC	4 ms	4 MB
g++	05_rand_00.in	AC	4 ms	4 MB
g++	05_rand_01.in	AC	4 ms	4 MB
g++	05_rand_02.in	AC	4 ms	4 MB
g++	05_rand_03.in	AC	4 ms	4 MB
g++	05_rand_04.in	AC	4 ms	4 MB
g++	05_rand_05.in	AC	4 ms	4 MB

Back to top page