逆元
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | ll exgcd(ll a,ll b,ll &x,ll &y) { if(b==0) { x=1,y=0; return a; } else { ll res=exgcd(b,a%b,y,x); y-=x*(a/b); return res; } } ll inv(ll a,ll n) { ll x,y; exgcd(a,n,x,y); return (x%n+n)%n; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | ll exgcd(ll a,ll b,ll &x,ll &y) { if(b==0) { x=1,y=0; return a; } else { ll res=exgcd(b,a%b,y,x); y-=x*(a/b); return res; } } ll inv(ll a,ll n) { ll x,y; exgcd(a,n,x,y); return (x%n+n)%n; } |