当前位置: 首页 > news >正文

初等数论--乘法逆元

1. 简介

乘法逆元,相同于在模除法做像倒数一样的操作。

比如:

对于模 5 : 4 5: \quad4 5:4的逆元是什么

1 4 ≡ v ( m o d 5 ) \frac{1}{4} \equiv v ( \bmod\ 5) 41v(mod 5)
也就是在模中除 4 4 4,相当于乘上一个什么样的数。
4 v ≡ 1 ( m o d 5 ) 4v \equiv 1 ( \bmod\ 5) 4v1(mod 5)

我们的目的是将模运算中要进行的除操作转换成乘。

根据裴蜀定理我们知道,只有当 gcd ⁡ ( 4 , 5 ) = 1 \gcd(4,5)=1 gcd(4,5)=1时,

v v v才可能有解,也就是有逆元。

因此我们可以用扩展欧几里得来求逆元。

下面的代码以luoguo p3811为例。

2. 扩展欧几里得求逆元

这里直接用扩展欧几里得就可以了,只要 gcd ⁡ ( a , m ) = 1 \gcd(a,m)=1 gcd(a,m)=1就可以了。

也就是对应着 x x x的值,不过 x x x的值有可能是负的,所以需要加上 m m m

#include <iostream>
#include <vector>int exgcd(int a, int b, int &x, int &y) {if (0 == b) {x = 1;y = 0;return a;}// int x_1;// int y_1;// int d = exgcd( b,a %b, x_1, y_1);// x = y_1;// y = x_1 - (a / b) * y_1;int d = exgcd( b, a % b, y, x);y -= (a / b) * x;return d;
}int main()
{int n;int p;std::cin >> n >> p;std::vector<int> mem(p, 0);int rev,y;for(int i = 1;i <= n;i++) {if ( i < p) {exgcd( i, p, rev, y);if (rev < 0)rev += p;mem[i] = rev;}std::cout << mem[i % p] << '\n';}return 0;
}

3. 费马小定理求乘法逆元

根据费马小定理我们有:

p i s p r i m e gcd ⁡ ( a , p ) = 1 ⇒ p ∣ a p − 1 − 1 ⇒ a p − 1 ≡ 1 ( m o d p ) p \ is \ prime\\ \gcd(a,p)=1 \Rightarrow\\ p \mid a^{p-1}-1 \Rightarrow a^{p-1} \equiv 1 (\ \bmod \ p) p is primegcd(a,p)=1pap11ap11( mod p)

因此此时有:
a p − 2 a ≡ 1 ( m o d p ) a^{p-2} a \equiv1 ( \ \bmod \ p) ap2a1( mod p)

a a a的乘法逆元此时为 a p − 2 a^{p-2} ap2

需要注意的是我们的模数需要是质数,才能用。

#include <cstdio>
#include <vector>using ll = long long;ll fpow(ll base, ll cnt, ll mod) {if (1 == base)return 1;ll tmp = base;ll ans = 1;while (cnt) {if (cnt & 1) ans  = (ans * tmp) % mod;tmp  = (tmp * tmp) % mod;cnt >>= 1;}return ans;
}int main()
{long long  n;long long p;scanf("%lld%lld", &n, &p);for (int i = 1;i <= n; i++) {printf("%lld\n", fpow(i, p - 2, p));}return 0;
}

4. 积性函数求乘法逆元

我们容易证明求乘法逆元是积性函数

a × i n v ( a ) ≡ 1 ( m o d p ) b × i n v ( v ) ≡ 1 ( m o d p ) a b × i n v ( b ) i n v ( a ) ≡ 1 ( m o d p ) i n v ( a b ) = i n v ( a ) i n v ( b ) a \times inv(a) \equiv 1 \ (\ \bmod\ p)\\ b \times inv(v) \equiv 1 \ (\ \bmod\ p)\\ ab \times inv(b) inv(a) \equiv 1 \ (\ \bmod\ p) \\ inv(ab) = inv(a) inv(b) a×inv(a)1 ( mod p)b×inv(v)1 ( mod p)ab×inv(b)inv(a)1 ( mod p)inv(ab)=inv(a)inv(b)

递推式
p = k i + r k i + r ≡ 0 ( m o d p ) − k i ≡ r ( m o d p ) ( p − k ) i ≡ r ( m o d p ) \begin{align*} p &=ki+r \\ ki+r &\equiv 0 \ ( \ \bmod\ p ) \\ -ki &\equiv r \ (\ \bmod\ p) \\ (p-k)i & \equiv r \ (\ \bmod \ p) \end{align*} pki+rki(pk)i=ki+r0 ( mod p)r ( mod p)r ( mod p)
两边同乘 i n v ( i r ) inv(ir) inv(ir)整理后可得
( p − k ) i × i n v ( i r ) ≡ r × i n v ( i r ) ( p − k ) i × i n v ( i ) i n v ( r ) ≡ r × i n v ( r ) i n v ( i ) i n v ( i ) ≡ ( p − k ) i n v ( r ) ⇔ i n v ( i ) ≡ ( p − ⌊ p / i ⌋ ) i n v ( r ) \begin{align*} (p-k)i \times inv(ir) &\equiv r \times inv(ir) \\ (p-k)i \times inv(i)inv(r) &\equiv r \times inv(r)inv(i) \\ inv(i) \equiv (p-k)inv(r) &\Leftrightarrow\\ inv(i) &\equiv(p - \lfloor p / i\rfloor) inv(r) \end{align*} (pk)i×inv(ir)(pk)i×inv(i)inv(r)inv(i)(pk)inv(r)inv(i)r×inv(ir)r×inv(r)inv(i)(pp/i⌋)inv(r)
于是代码

#include <cstdio>
#include <vector>long long inv[3000001];int main()
{long long  n;long long p;scanf("%lld%lld", &n, &p);inv[1] = 1;for ( int i = 1;i <= n; i++) {if ( i != 1) {inv[i] = (p - p / i) * inv[ p % i] % p;}printf("%lld\n", inv[i]);}return 0;
}
4.1 阶乘求逆元

告别地在求阶乘逆元的时候,可以先求出最大的,再反向逆推回去。

也就是下面的式子成立

i n v ( n ! ) × n × ( n − 1 ) ! ≡ 1 i n v ( n ! ) × n = i n v ( ( n − 1 ) ! ) i n v ( i ! ) = ( i + 1 ) × i n v ( ( i + 1 ) ! ) inv(n!) \times n \times(n-1)! \equiv1\\ inv(n!) \times n =inv((n-1)!)\\ inv(i!) =(i+1)\times inv((i+1)!) inv(n!)×n×(n1)!1inv(n!)×n=inv((n1)!)inv(i!)=(i+1)×inv((i+1)!)

代码

	fac[1] = 1;ifac[1] = 1;for (int i = 2; i <= MAXN; i++) {fac[i] = fac[i - 1] * i % MOD; }ll y;exgcd( fac[MAXN], MOD, ifac[MAXN], y);for (int i = MAXN - 1; i > 1; i--) {ifac[i] = ifac[i + 1] * (i + 1) % MOD;}

5. 参考

czc1999
let_life_stop


http://www.mrgr.cn/news/91889.html

相关文章:

  • Ubuntu 22.04 Install deepseek
  • RT-Thread+STM32L475VET6实现红外遥控实验
  • ROS 2入门 - 机器人操作系统ROS2的安装
  • Blender小技巧和注意事项
  • 【拜读】Tensor Product Attention Is All You Need姚期智团队开源TPA兼容RoPE位置编码
  • 单元测试整理
  • QT基础八、与时间相关的UI控件
  • DeepSeek掘金——SpringBoot 调用 DeepSeek API 快速实现应用开发
  • PrimeTime:工具简介
  • 华为昇腾910b服务器部署DeepSeek翻车现场
  • nodejs npm install、npm run dev运行的坎坷之路
  • 【AI学习】AI大模型新时代,怎样更好地熟练地使用指令工具?
  • python的if判断和循环语句(while循环和for循环)
  • 【练习】【回溯:组合:不同集合】力扣 17. 电话号码的字母组合
  • 【Java学习】多态
  • GCC编译器(含预处理/编译/汇编/链接四阶段详解)
  • 算法题(74):Pow(x,n)
  • 一文说清楚编码、摘要、加密、公钥、私钥、解密、签名、验签
  • 对免认证服务提供apikey验证
  • 大数据学习之任务流调度系统Azkaban、Superset可视化系统