乘法逆元超详解一，模运算的性质二，除法的模运算？三，乘法逆元的性质

66 阅读 0 评论 44 点赞

我是靠谱客的博主天真睫毛，这篇文章主要介绍乘法逆元超详解一，模运算的性质二，除法的模运算？三，乘法逆元的性质，现在分享给大家，希望可以做个参考。

一，模运算的性质

二，除法的模运算？

1.除法模运算

2.解决除法模运算问题

三，乘法逆元的性质

1，乘法逆元总存在吗？

2.什么时候一定存在乘法逆元

三，求乘法逆元

1.费马小定理

1.1 C++ 由费马小定理求乘法逆元（p为质数时）

输入输出样例

2.扩展欧几里得算法

2.1 求逆元代码

3.线性求逆元

3.1 求逆元

3.乘法逆元应用

一，模运算的性质

1. (a+b)%p=(a%p+b%p)%p

2. (a-b)%p=(a%p-b%p)%p

注意：(9-7)%8=(9%8-7%8)%8=-6 ;不是我们要的值，这时要加上p,改为：

3. (a-b)%p=（ (a%p-b%p) % p + p ）%p

4. (a*b)%p=((a%p)*(b%p))%p

二，除法的模运算？

1.除法模运算

(a/b)%p=(a%p)/(b%p) ,如果我们保证可以整除，它是否成立呢？

取a=8,b=2,p=6; 左式=4，右式=1；也就是说 除法的模运算不一定成立。

2.解决除法模运算问题

能否将除法转化为乘法？找到 binv ,使得 （a/b）%p==(a*binv)%p ；若能，则称 binv 为 b在模p意义下的乘法逆元；

三，乘法逆元的性质

(1) 设 ( a / b ) $equiv$ x ( mod p) ；即 (a / b ) %p=x % p ;

(2) 设存在 b $_{inv}$ ，满足 a*b $_{inv}$ $equiv$ x ( mod p)

(1)*b : a $equiv$ bx ( mod p) ……（3）

(2)*b : a*b $_{inv}$ *b $equiv$ bx ( mod p ) ……（4）

(4)-(3) : a*( b $_{inv}$ *b -1 ) $equiv$ 0 ( mod p ) ……(5)

因为我们在找b的乘法逆元，而 a 是任意的数，所以为了使 (5) 恒成立，则 ( b $_{inv}$ *b -1 ) $equiv$ 0

即 b $_{inv}$ * b $equiv$ 1 （ mod p）; 此时 binv 就是 b在模p意义下的乘法逆元；

1，乘法逆元总存在吗？

对于 b $_{inv}$ * b $equiv$ 1 （ mod p），是否总存在这样的 b $_{inv}$ ?

取 b=2,p=10 则 2 * b $_{inv}$ $equiv$ 1 （ mod 10），即不存在。

2.什么时候一定存在乘法逆元

若存在乘法逆元，则必满足 b $_{inv}$ * b $equiv$ 1 （ mod p）；

则设 b $_{inv}$ * b $equiv$ k*p + 1 ……（1）;

设g为b,p的最大公约数，即 g = gcd ( b , p ) ……（2）;

则 g* b $_{inv}$ * b $equiv$ g*k*p + 1 ……（3）；

g( b $_{inv}$ * b-k*p)=1……（4）我们是在整数范围讨论的，所以（4）式成立当且仅当

g=1 && b $_{inv}$ * b-k*p =1

结论：乘法逆元存在当且仅当 b与p互质

三，求乘法逆元

1.费马小定理

（1）…… b $_{inv}$ * b $equiv$ 1 （ mod p）

（2）……费马小定理：若 p 为质数，则 a $^{p-1}$ $equiv$ 1 ( mod p) ;

由（2）得： a*a $^{p-2}$ $equiv$ 1 ( mod p) ;

则结合（1）有 b $_{inv}$ = b $^{p-2}$ 满足 (1)式；

1.1 C++ 由费马小定理求乘法逆元（p为质数时）

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
using namespace std;
typedef long long ll;
ll fast_pow(ll a, ll b, ll p)//快数幂算法
{
ll ans = 1;
a %= p;
while (b)
{
if (b & 1)
{
ans = (ans * a) % p;
}
a = (a * a) % p;
b >>= 1;
}
return ans;
}
ll get_inv(ll x, ll p)
{
return fast_pow(x, p - 2, p);
}
int main()
{
ll x, p;
cin >> x >> p;
for (int i = 1; i <= x; i++)
{
cout<<get_inv(i, p)<<endl;
}
}

输入格式：

一行n,p

输出格式：

n行,第i行表示i在模p意义下的逆元。

输入输出样例

输入样例#1：

复制代码

1
10 13

输出样例#1：

复制代码

2.扩展欧几里得算法

（1）扩展欧几里得算法：求 ax+by=gcd(a,b) ……（1）的一组 x,y；

（2）求a 在模 p 意义下的乘法逆元：（这里改求 a 防止字符混淆）

a*a $_{inv}$ $equiv$ 1 ( mod p ) ……（2）

由（2）得： a*a $_{inv}$ +p*y=1 ……（3）

已知a , p 互质，即 gad(a,p)=1 ……（4）

（3），（4）得 a*a $_{inv}$ +p*y=gcd(a,b)=1 ，对照欧几里得公式，得 不需要 p为质数，但要求 a , p互质，即乘法逆元存在即可。

2.1 求逆元代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
using namespace std;
typedef long long ll;
void exgcd(ll a, ll b, ll& x, ll& y)
{
if (b == 0)
{
x = 1;
y = 0;
return;
}
exgcd(b, a % b, y, x);
y -= (a / b) * x;
}
ll get_inv(ll a, ll p)
{
ll x = 1, y = 0;
exgcd(a, p, x, y);
return (x % p + p) % p;//防止出现负数
}
int main()
{
ll a, p;
cin >> a >> p;
for (int i = 1; i <= a; i++)
{
cout<<get_inv(i, p)<<endl;
}
}

3.线性求逆元

（1）求1~n 依次在模p意义下得逆元;

（2）题目保证 p 为质数，且 p>n;

（3）上述两种方法略慢，因为需要对每一个数求逆元

（1）对于一个数。由于 p>x。设 p = kx + r, k = $left [ frac{p}{r} right ]$ , r = p % x ;

（2）在模 p 的意义下：

kx + r $equiv$ 0 ( mod p ) $leftrightarrow$ kx $equiv$ -r ( mod p ) $leftrightarrow$ k * r $_{inv}$ * x $equiv$ -1 $equiv$ -x * x $^{_{_{inv}}}$ ( mod p )

x* $tfrac{k}{r}$ $equiv$ -x * x $_{inv}$ ( mod p )

$leftrightarrow$

r $_{inv}$ *k*x= -x * x $_{inv}$ ( mod p )

$leftrightarrow$

x $_{inv}$ $equiv$ -k * r $^{inv}$ ( mod p )

这里我们得到一个递推式，如果知道 r $_{inv}$ 的值，我们就能得到 x $_{inv}$ 的值。

根据假设， r = p % x <x,因此我们如果依次求 1~n 的逆元，那么 r $_{inv}$ 一定比 x $_{inv}$ 先被求出。即求 x $_{inv}$ 时已经知道 r $_{inv}$ 的值。

注意到若按等式处理，满足等式的 x $_{inv}$ 应为负数？不是的，我们做一下变化

x $_{inv}$ $equiv$ ( -k * r $^{inv}$ ( mod p ) + p ) % p

3.1 求逆元

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
using namespace std;
typedef long long ll;
const int MAXN = 2e5;
int n, p;
int inv[MAXN];
void niyuan(int n)
{
inv[1] = 1;
for (int i = 2; i <= n; i++)
{
inv[i] = -(p / i) * inv[p % i]; //x_inv= -k * r_inv ;
inv[i] = (inv[i] % p + p) % p;
}
}
void printNiyuan(int n)
{
for (int i = 1; i <= n; i++)
{
cout << inv[i] << " ";
}
}
int main()
{
cin >> n >> p;
niyuan(n);
printNiyuan(n);
}

3.乘法逆元应用

适用于很大的数的乘积，最后的值的 p取模输出，例如求排列组合的个数

最后

以上就是天真睫毛最近收集整理的关于乘法逆元超详解一，模运算的性质二，除法的模运算？三，乘法逆元的性质的全部内容，更多相关乘法逆元超详解一，模运算内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：数论
浏览次数：66 次浏览
发布日期：2024-08-11 02:45:01
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_7_o_18_f5_14_zkx.html

乘法逆元超详解一，模运算的性质二，除法的模运算？三，乘法逆元的性质

一，模运算的性质

二，除法的模运算？

1.除法模运算

2.解决除法模运算问题

三，乘法逆元的性质

1，乘法逆元总存在吗？

2.什么时候一定存在乘法逆元

三，求乘法逆元

1.费马小定理

1.1 C++ 由费马小定理求乘法逆元（p为质数时）

输入输出样例

2.扩展欧几里得算法

2.1 求逆元代码

3.线性求逆元

3.1 求逆元

3.乘法逆元应用

最后

评论列表共有 0 条评论

发表评论取消回复

乘法逆元超详解一，模运算的性质二，除法的模运算？三，乘法逆元的性质

一，模运算的性质

二，除法的模运算？

1.除法模运算

2.解决除法模运算问题

三，乘法逆元的性质

1，乘法逆元总存在吗？

2.什么时候一定存在乘法逆元

三，求乘法逆元

1.费马小定理

1.1 C++ 由费马小定理求乘法逆元（p为质数时）

输入输出样例

2.扩展欧几里得算法

2.1 求逆元代码

3.线性求逆元

3.1 求逆元

3.乘法逆元应用

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

微信扫一扫：分享

发表评论取消回复