快速幂求逆元与逆元

本文主要是介绍快速幂求逆元与逆元，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

我上一篇博客链接写的是多个数求乘法逆元而快速幂求逆元用于单个数求乘法逆元

逆元是对分数取模用的

	对于除法取模不成立，即(a/b)%p≠(a%p/b%p)%p。求逆元的思路：(一般ACM的题目都是对1e9+7这种素数取模，所以gcd(a,p)==1)a*b=1(mod p) => b=1/a(mod p)。根据费马小定理：b^(p-1)=1(mod p) => b^(p-2)=1/b(mod p)可以看出来逆元1/b (mod p)=b^(p-2)可以得出a/b对质数p取模就是 a*b^(p-2) mod p 。

2024CCPC郑州邀请赛-Problem H. 随机栈用到了逆元但当时没有想到没有写出来

代码如下

#include<iostream>
#include<queue>
#include<algorithm>
#include<map>
# define int long long
using namespace std;
int mod = 998244353;
map<int, int> m;
int asd(int a, int b) 
{int sum = 1;while(b){if(b%2==0){a=a*a%mod;b=b/2;}else{b=b-1;sum=sum*a%mod;b=b/2;a=a*a%mod;}}return sum%mod;
}
signed  main() {priority_queue<int, vector<int>, greater<int> > p;int n, num, l = -1, t = 0, s = 1, x = 1;cin >> n;for (int i = 0; i < 2 * n; i++) {cin >> num;if (t != 1){if (num == -1) {s = s * m[p.top()] % mod;x = x * p.size() % mod;if (p.top() >= l) {l = p.top();m[p.top()]--;p.pop();}elset = 1;} else {p.push(num);m[num]++;}}}if (t == 1)cout << "0" << endl;else {int ans = s * asd(x, mod - 2) % mod;cout << ans << endl;}}

这篇关于快速幂求逆元与逆元的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---