求逆元算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了求逆元算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2830字，纯文字阅读大概需要5分钟。
内容图文
费马小定理：若p是素数，a是正整数且不能被p整除，则ap-1 == 1(mod p)
费马小定理的拓展：ap == a(mod p)
欧拉定理：对任意互素的a和n. 设Φ(n) 为小于n且与n互素的正整数的个数，有aΦ(n) == 1(mod n)
欧拉定理的拓展：aΦ(n)+1 == a(mod n)
求乘法逆元的作用：除以一个数 再取模时，可以将这个数乘以这个数的逆元 再取模（将除法转化成乘法运算）
为什么要这样等价：对于 (a/b)% mod 这个式子，是不可以等价为 ((a%mod) / (b%mod))%mod 的 (例如：a=3，b=2，mod=3)，但是可以写为(a*b-1)%mod，其中b-1表示b的逆元。这就是逆元的作用
引用计蒜客某题面：
什么是乘法逆元：a*x = 1（mod C），那么称 x 为 a 对 C 的乘法逆元
e.g. a = 4，C = 7 则逆元 x = 2;
4*2=1(mod 7) 12/4%7 = (12*2)%7 (除法换乘法）
用一道入门题来来学习三中模板：https://www.luogu.org/problem/P3811
模板一：
线性打表递推法：（递推公式：inv[i] = (p-p/i) * inv[p%i] % p )
这种方法最快，但是耗费的空间多
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <string>
5 #include <ctime>
6 #include <climits>
7 #include <utility>
8 #include <deque>
9 #include <queue>
10 #include <map>
11 #include <algorithm>
12 #include <functional>
13usingnamespace std;
14 typedef longlong ll;
1516 ll inv[3000006];
17int main()
18{
19 ll a, p;
20while(~scanf("%lld %lld", &a, &p) )
21 {
22 memset(inv, 0, sizeof(inv));
23 inv[0] = 1;
24 inv[1] = 1;
25for(ll i=2; i<=a; i++ )
26 inv[i] = (p-p/i)*inv[p%i]%p;
27for(ll i=1; i<=a; i++ )
28 printf("%lld\n", inv[i]);
29 }
30return0;
31 }
模板二：
拓展欧几里得算法
这道题我用这个方法TLE了，这个次慢
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <string>
5 #include <ctime>
6 #include <climits>
7 #include <utility>
8 #include <deque>
9 #include <queue>
10 #include <map>
11 #include <algorithm>
12 #include <functional>
13usingnamespace std;
14 typedef longlong ll;
1516void exgcd(ll a, ll b, ll &x, ll &y)
17{
18if( b==0 )
19 {
20 x=1;
21 y=0;
22return ;
23 }
24 exgcd(b, a%b, y, x);
25 y -= (a/b)*x;
26return ;
27}
2829int main()
30{
31 ll a, p;
32 ll x, y;
33while( ~ scanf("%lld %lld", &a, &p) )
34 {
35for(ll i=1; i<=a; i++ )
36 {
37 exgcd(i, p, x, y);
38 x = (x%p+p)%p;
39 printf("%lld\n", x);
40 }
41 }
42return0;
43 }
模板三：
费马小定理算法：（快速幂（a，p-2，p）），前提是a p互质，这个也TLE了，这个最慢
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <string>
5 #include <ctime>
6 #include <climits>
7 #include <utility>
8 #include <deque>
9 #include <queue>
10 #include <map>
11 #include <algorithm>
12 #include <functional>
13usingnamespace std;
14 typedef longlong ll;
1516ll fpm(ll x, ll power, ll mod)
17{
18 ll ans = 1;
19for( ; power; power>>=1,(x*=x)%=mod )
20if( power&1 )
21 (ans*=x)%=mod;
22return ans;
23}
2425int main()
26{
27 ll a, p;
28 ll x, y;
29while( ~ scanf("%lld %lld", &a, &p) )
30 {
31for(ll i=1; i<=a; i++ )
32 {
33 printf("%lld\n", fpm(i,p-2,p));
34 }
35 }
36return0;
37 }
原文：https://www.cnblogs.com/wsy107316/p/11520602.html
内容总结
以上是互联网集市为您收集整理的求逆元算法全部内容，希望文章能够帮你解决求逆元算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。