This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ruthen71/rcpl
#include "math/inv_mod.hpp"
#pragma once #include <cassert> #include "math/extended_gcd.hpp" // mod >= 2 long long inv_mod(long long a, long long mod) { a %= mod; if (a < 0) a += mod; assert(a != 0); auto [x, y, g] = extended_gcd(a, mod); x %= mod; if (x < 0) x += mod; return x; }
#line 2 "math/inv_mod.hpp" #include <cassert> #line 2 "math/extended_gcd.hpp" #include <tuple> // find (x, y) s.t. ax + by = gcd(a, b) // a, b >= 0 // return {x, y, gcd(a, b)} template <class T> std::tuple<T, T, T> extended_gcd(T a, T b) { if (b == 0) return {1, 0, a}; auto [y, x, g] = extended_gcd(b, a % b); return {x, y - (a / b) * x, g}; } #line 5 "math/inv_mod.hpp" // mod >= 2 long long inv_mod(long long a, long long mod) { a %= mod; if (a < 0) a += mod; assert(a != 0); auto [x, y, g] = extended_gcd(a, mod); x %= mod; if (x < 0) x += mod; return x; }