math/extGCD.hpp

• View this file on GitHub
• Last update: 2024-02-10 23:01:10+09:00
• Include: #include "math/extGCD.hpp"

Verified with

• test/extGCD.test.cpp

Code

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

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);
}

#line 2 "math/extGCD.hpp"
#include<bits/stdc++.h>
using namespace std;

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);
}

Back to top page