扩展欧几里得算法

1
2
3
4
5
void exgcd(LL a,LL b,LL &d,LL &x,LL &y)
{
if(!b){ d=a;x=1;y=0; }
else{ exgcd(b,a%b,d,y,x); y-=x*(a/b); }
}

逆元

对于正整数 a和m,若$ax \equiv 1 \pmod m$
那么这个同余方程中的x的最小正整数解成为a模m的逆元

p.s. 可以理解为mod m意义下的倒数

公式

已知$b|a$
$\frac{a}{b} \pmod m = \frac{a \pmod mb}{b}$

扩展欧几里得

  • 要求$gcd(a,m) = 1$
1
2
3
4
5
6
LL inv(LL a,LL m)
{
LL d,x,y;
d = exgcd(a,m,d,x,y);
return d==1 ? (x+m) % m : -1;
}

费马小定理

  • 要求p为质数

因为 $a^{m-1} \equiv 1 \pmod m$
所以 $\frac{1}{a} \equiv a^{m-2} \pmod m$

inv = pow_mod(a,m-2,m)

递推

求1-m的逆元

m为奇质数,复杂度$O(m)$

$inv[1] = 1,inv[i] = (m - m/i)*inv[m \pmod i] \pmod m$

求阶乘逆元

已知$invf[m]$,倒推求 1! - m! 逆元

$invf[i] = (i+1)invf[i+1] \pmod m$

指数循环节

$a^b \equiv a^{b \pmod {\phi(m)} +\phi(m)} \pmod m , b \geq \phi(m)$

和循环节有关,一般b比较大时采用

a*b %mod

若a*b爆long long,则用这个方法求

1
2
3
4
5
6
7
8
9
10
11
12
13
LL mul_mod(LL a,LL b,LL m) //防止long long溢出
{
a%=m; b%=m;
LL res = 0;
while(b)
{
if(b&1) res = (res+a) % m;
b >>= 1;
a <<= 1;
if(a>=m) a%=m;
}
return res;
}

或者直接开long double

1
2
3
4
LL mul_mod(LL a,LL b,LL m)
{
return a*b-(long long)((long double)a/m*b+eps)*m;
}

p.s. 慎用

参考资料