模板/知识库

逆元

求x在%p意义下的逆元

即x^(p-2)

1
2
3
4
5
6
7
8
9
10
#define md(a) (((a)%p+p)%p)
inline ll po(ll x){
ll y=mo-3,ans=x,t=x;
while(y>0){
if(y&1)ans=md(ans*t);
y=y>>1;
t=md(t*t);
}
return ans;
}

位运算

位运算