This documentation is automatically generated by competitive-verifier/competitive-verifier
一次不定方程式 $ax+by=c$ の 1 つの整数解 $(x,y)$ を求める.
extgcd(a, b, x, y)
:$ax+by=\gcd(|a|,|b|)$ の解のうち,$|x|+|y|$ が最小なものを x
, y
に格納し,$\gcd(|a|,|b|)$ を返す.extgcd(a, b, c, x, y)
:$ax+by=c$ の 1 つの解を x
, y
に格納し,$\gcd(|a|,|b|)$ を返す.整数解が存在しない場合は $-1$ を返す.このとき,一般解は $(x,y) = (x_0+b’t,\ y_0-a’t)$
extgcd(a, b, c, x, y)
の最後の処理の正当性本来は
x *= c / d;
y *= c / d;
とすべきだが,x * c / d
が大きくオーバーフローする可能性がある場合も,a
の大きさによっては以下の処理でオーバーフローの可能性を低くすることができる.
x *= c % a / d;
y *= c % a / d;
x += c / a;
これの正当性を以下に示す.
#pragma once
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
long long extgcd(long long a, long long b, long long &x, long long &y) {
long long x_ = abs(a), xd = 1, xdd = 0, y_ = abs(b), yd = 0, ydd = 1, div;
while(true) {
if(!y_) {
x = xd;
y = xdd;
return x_;
}
div = x_ / y_;
x_ -= div * y_;
xd -= div * yd;
xdd -= div * ydd;
if(!x_) {
x = yd;
y = ydd;
return y_;
}
div = y_ / x_;
y_ -= div * x_;
yd -= div * xd;
ydd -= div * xdd;
}
if(a < 0) x = -x;
if(b < 0) y = -y;
}
long long extgcd(long long a, long long b, long long c, long long &x, long long &y) {
long long d = extgcd(a, b, x, y);
if(c % d) return -1;
if(a != 0) {
x *= c % a / d;
y *= c % a / d;
x += c / a;
}
else {
y *= c / d;
}
return d;
}
#line 2 "math/extgcd.cpp"
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
long long extgcd(long long a, long long b, long long &x, long long &y) {
long long x_ = abs(a), xd = 1, xdd = 0, y_ = abs(b), yd = 0, ydd = 1, div;
while(true) {
if(!y_) {
x = xd;
y = xdd;
return x_;
}
div = x_ / y_;
x_ -= div * y_;
xd -= div * yd;
xdd -= div * ydd;
if(!x_) {
x = yd;
y = ydd;
return y_;
}
div = y_ / x_;
y_ -= div * x_;
yd -= div * xd;
ydd -= div * xdd;
}
if(a < 0) x = -x;
if(b < 0) y = -y;
}
long long extgcd(long long a, long long b, long long c, long long &x, long long &y) {
long long d = extgcd(a, b, x, y);
if(c % d) return -1;
if(a != 0) {
x *= c % a / d;
y *= c % a / d;
x += c / a;
}
else {
y *= c / d;
}
return d;
}