求逆元模板
void exgcd(ll a, ll b, ll &x, ll &y) //拓展欧几里得算法 { if(!b) x = 1, y = 0; else { exgcd(b, a % b, y, x); y -= x * (a / b); } } ll niyuan(ll a, ll b) //求a对b取模的逆元 { ll x, y; exgcd(a, b, x, y); return (x + b) % b; }
void exgcd(ll a, ll b, ll &x, ll &y) //拓展欧几里得算法 { if(!b) x = 1, y = 0; else { exgcd(b, a % b, y, x); y -= x * (a / b); } } ll niyuan(ll a, ll b) //求a对b取模的逆元 { ll x, y; exgcd(a, b, x, y); return (x + b) % b; }
相关推荐