逆元模板

xiaoxiao2021-02-28  7

 逆元是求ax≡1(mod p)中的x的最小正整数,常应用于 除法取模。

   存在这样的x的条件是a与p互素,即只有当a与p互素时,逆元存在

   求逆元有三种常用的方式

   扩展欧几里德(要求a与p互素)

int extgcd(int a, int b, int &x, int &y)//有返回值 { int d = a; if(b != 0) { d = extgcd(b, a%b, y, x); y -= (a / b) * x; } else x = 1, y = 0; return d; } int mod_inv(int a, int p) { int x, y; extgcd(a, p, x, y); return (x%p + p) % p; } void exgcd(LL a,LL b,LL &x,LL &y)//扩欧,无返回值 { if(b==0) { y=0;x=1; } else { exgcd(b,a%b,y,x); y-=x*(a/b); } }

费马小定理(要求p为素数,且a与p互素)

 

LL mod_pow(LL a, LL b, LL p) { LL ans = 1; a %= p; while(b>0) { if(b & 1) ans = ans * a % p; a = a * a % p; b >>= 1; } return ans; } LL mod_inv(LL a, LL p) { return mod_pow(a, p-2, p); }

线性时间求逆元(要求p为素数,常用于a较小且需要求出大量逆元的时候)

const int N=50010; int inv[N]; void inv_init(int p) { inv[1] = 1; for(int i = 2; i < N; i++) inv[i] = (p - p / i) * inv[p % i] % p; }
转载请注明原文地址: https://www.6miu.com/read-2250115.html

最新回复(0)