求逆元的两种方法

2019-04-14 08:49发布

站内文章 / 模拟电子
13653 0 1267
方法1：

扩展欧几里德

只能用于求a < p的情况，而且要求a与p互质 int inv(int a, int p) { if(a == 1) return 1; return inv(p%a, p) * (p-p/a) % p; }
方法2：

费马小定理

a^(p-1)=1(% p)  =>  a^(p-2) = 1/a(% p) => a^(p-2) = a^(-1)(% p)

a的模p逆元就是a^(p-2)，要求a与p互质
int pow_p(int a, int b, int c) // a^b % c { int s = 1; while(b > 0) { if(b % 2) s *= a; a *= a; b /= 2; } return s; } int inv(int a, int p) { return pow_p(a, p-2, p); //a^(p-2) % p }

热门文章