推荐视频：模意义下的乘法逆元
特点：除以一个数取模等于乘以这个数的逆元取模：a/n%mod==a* n^(mod-2)%mod(费马小定理)
1.费马小定理
前提：p为质数
n的逆元等于n^(p-2)
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int mod=998244353;
int _pow(int a,int b=mod-2){
int ans=1;
while(b){
if(b&1) ans=(1LL*ans*a)%mod;
a=1LL*a*a%mod;
b>>=1;
}
return ans;
}
int main(){
int n;
cin>>n;
if(mod%n){
cout<<_pow(n);
}
return 0;
}
扩展偶
++
<++>
线性求1-n的逆元
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=2e5+10,mod=998244353;
int inv[N];
int main(){
int n;
cin>>n;
inv[1]=1;
for(int i=2;i<=n;i++){
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}
return 0;
}