逆元
- 多用
- POWERMOD(X,Y,Z)
- GCDEX(a,b,&x,&y)
- 费马小定理求逆元
- FERMINV(a)
- 扩展欧几里得求逆元
- GCDINV(a,p)
- 逆元线性筛
- 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
|
页阅读量: 30 ・
站访问量: 2942 ・
站访客数: 1670