学过OI，……我便考你一考。逆元的求法，怎样写的？
不能写罢？……我教给你，记着！这些算法应该记着。将来打国赛的时候，写代码要用。 “谁要你教，不是 a^{-1} \equiv a^{p-2} \pmod{p} a − 1 ≡ a p − 2 ( mod p ) 么？” XJ 显出极高兴的样子，将两个指头的长指甲敲着键盘，点头说，“对呀对呀！……求逆元有四种写法，你知道么？” 法1：费马小定理 对于指数 p p ，有 a^{p-1} \equiv 1 \pmod{p} a p − 1 ≡ 1 ( mod p ) ，故有 a^{-1} \equiv a^{p-2} \pmod{p} a − 1 ≡ a p − 2 ( mod p ) 。 代码： ll mpow (ll x,ll y) { ll ans= 1 ; for (;y;y>>= 1 ,x=x*x%p) if (y& 1 ) ans=ans*x%p; } ll inv (ll x) { return mpow (x,p -2 ); } 优点：代码简单，速度较快 缺点：仅适合 p p 为质数的情况 法2：exgcd 令 x=a^{-1} x = a − 1 ，则 ax \equiv 1 \pmod{p} a x ≡ 1 ( mod p ) ，即 ax-py=1 a x − p y = 1 ，由于 a,p a , p 均为常数，所以可以直接利用 exgcd 算法求出 x x ，注意特判 x x 和 p p 不互质的情况即可。 代码： ll exgcd (ll a,ll b,ll &x,ll &y) { if (!b) {x= 1 ,y= 0 ; return a;} ll v= exgcd (b,a%b,x,y),t=x-a/b*y; x=y,y=t; return v; } ll inv (ll x) { ll t1,t2; if ( exgcd (x,p,t1,t2)!= 1 ) return -1 ; return (t1%p+p)%p; } 优点...