数论 | 模逆元
还可记作:
模运算的部分性质
上面三条性质,相当于加、减、乘、乘方都齐了,那么除呢?
这就需要模逆元来解决。
模逆元
类比倒数
那么如果知道
求法
费马小定理 (Fermat's Little Theorem)
若
为质数,整数 与 互质,则 另一种形式:对于任意整数
,有
由以上定理:
左边提出一个
因此可得出:
因此
例如要求
注意:
- 满足整数
与 互质,才存在逆元,否则逆元不存在。 为质数才可使用费马小定理计算逆元,否则需要使用扩展欧几里得算法求逆元。
快速幂
在实际题目中,模
#define MOD 20220211
long long fastpow(long long a, long long b)
{
a %= MOD; // 开头先取一次模
long long ans = 1;
while (b)
{
if (b % 2 == 1)
ans = ans * a % MOD; // 每次运算都取模
a = a * a % MOD; // 每次运算都取模
b >>= 1;
}
return ans;
}
本文采用 CC BY-SA 4.0 许可,本文 Markdown 源码:Haotian-BiJi