src/math/ext_gcd.hpp

• View this file on GitHub
• Last update: 2022-12-18 20:53:53+09:00
• Include: #include "src/math/ext_gcd.hpp"

Verified with

• test/aoj/ntl_1_e.test.cpp

Code

#pragma once

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

template <typename T = long long> T ext_gcd(T a, T b, T &x, T &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = ext_gcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}

#line 2 "src/math/ext_gcd.hpp"

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

template <typename T = long long> T ext_gcd(T a, T b, T &x, T &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = ext_gcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}

Back to top page