Math/inv_mod.hpp

• View this file on GitHub
• Last update: 2023-04-05 23:10:22+09:00
• Include: #include "Math/inv_mod.hpp"

Required by

• 離散対数 (log mod) (Math/log_mod.hpp)

Verified with

• test/yosupo_DiscreteLog.test.cpp

Code

ll inv_mod(ll a,ll m){
    ll b=m,u=1,v=0,t;
    while(b){
        t=a/b;
        swap(a-=t*b,b);swap(u-=t*v,v);
    }
    u%=m;
    if(u<0) u+=m;
    return u;
}

#line 1 "Math/inv_mod.hpp"
ll inv_mod(ll a,ll m){
    ll b=m,u=1,v=0,t;
    while(b){
        t=a/b;
        swap(a-=t*b,b);swap(u-=t*v,v);
    }
    u%=m;
    if(u<0) u+=m;
    return u;
}

Back to top page