郁郁青青 长过千寻

逆元

    数论
  1. 多用
    1. POWERMOD(X,Y,Z)
    2. GCDEX(a,b,&x,&y)
  2. 费马小定理求逆元
    1. FERMINV(a)
  3. 扩展欧几里得求逆元
    1. GCDINV(a,p)
  4. 逆元线性筛
    1. LININV(p)

多用

POWERMOD(X,Y,Z)

1
2
3
4
5
6
7
8
初始化res=1
x=x%z
while y!=0
   if y是奇数
      res=(res*x)%z
   y=y/2
   x=(x*x)%z
return res

GCDEX(a,b,&x,&y)

1
2
3
4
5
6
7
8
if b==0
   x=1
   y=0
   return a
gcd=GCDEX(b,a%b,x1,y1)
x=y1
y=x1-a/b*y1
return gcd

费马小定理求逆元

FERMINV(a)

1
2
初始化p为质数，求a关于p的逆元
return POWERMOD(a,p-2,p)

扩展欧几里得求逆元

GCDINV(a,p)

1
2
3
4
初始化x，y作为二元一次方程解，并且保证a，p互质
GCDEX(a,p,x,y)
x=(x%p+p)%p
return x

逆元线性筛

LININV(p)

1
2
3
4
初始化数组inv，inv[i]表示i关于p的逆元
inv[1]=1
for i=2 to p-1
   inv[i]=inv[p%i]*(p-p/i)%p
页阅读量:  ・  站访问量:  ・  站访客数: