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

• View this file on GitHub
• Last update: 2024-12-26 20:32:55+09:00
• Include: #include "daylight/math/extgcd.hpp"

Depends on

• 基本テンプレート (daylight/base.hpp)

Required by

• daylight/math/all.hpp

Verified with

• test/aoj/ntl/1_E.test.cpp

Code

#include "daylight/base.hpp"
/// @brief 拡張ユークリッドの互除法

/// @brief gcd(a,b)とax+by=gcd(a,b)を満たすx,yを求める
/// @param a 入力1つ目
/// @param b 入力2つ目
/// @param x 出力1つ目
/// @param y 出力2つ目
/// @return gcd(a,b)
ll extgcd(ll a, ll b, ll& x, ll& y) {
	ll d = a;
	if(b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	} else {
		x = 1;
		y = 0;
	}
	return d;
}

/// @brief 任意のmについてn^{-1} mod mを求める.
/// @param n 逆元を求めたい値
/// @param m 法(素数でなくてもよい)
/// @return 存在しなければ-1,存在するなら逆元
ll inv_extgcd(ll n, ll m) {
	ll x, y;
	ll G = extgcd(n, m, x, y);
	if(G != 1) {
		return -1;
	}
	if(x < 0) {
		x += (abs(x) + 2 * m) / m * m;
	}
	x %= m;
	return x;
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj_resolve/resolver.py", line 181, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 252, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 482, in update
    self.update(
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 477, in update
    raise BundleErrorAt(
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: daylight/base.hpp: line 103: unable to process #include in #if / #ifdef / #ifndef other than include guards

Back to top page