math/modinv.cpp

• View this file on GitHub
• Last update: 2020-04-26 17:42:59+09:00

Code

template<typename T>  
T mod_inv(T x, T M){  
   T u = 1, t = 1, v = 0, s = 0, m = M;  
   while (x) { T q = m/x; swap(s -= q*u, u); swap(t -= q*v, v); swap(m -= q*x, x); }  
   if(s < 0) s += M;  
   return s;  
}

#line 1 "math/modinv.cpp"
template<typename T>  
T mod_inv(T x, T M){  
   T u = 1, t = 1, v = 0, s = 0, m = M;  
   while (x) { T q = m/x; swap(s -= q*u, u); swap(t -= q*v, v); swap(m -= q*x, x); }  
   if(s < 0) s += M;  
   return s;  
}

Back to top page