逆元素是指一个可以取消另一给定元素运算的元素，在数学里，逆元素广义化了加法中的加法逆元和乘法中的倒数
传送门
若$a*x \equiv1 \pmod {b}$，且a与b互质，那么我们就能定义: x 为 a 的逆元，记为$a^{-1}$
有三种方法可以求逆元：
扩展GCD
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=2e5+5;
int a,p;
void Exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) x = 1, y = 0;
else Exgcd(b, a % b, y, x), y -= a / b * x;
}
int main(){
ll x, y;
scanf("%d%d",&a,&p);
Exgcd (a, p, x, y);
x = (x % p + p) % p;
printf ("%d\n", x);
return 0;
}
|
费马小定理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll p,n;
ll mod_pow(ll x,ll n,ll mod){
ll res=1;
while(n>0){
if(n&1) res=res*x%mod;
x=x*x%mod;
n>>=1;
}
return res;
}
int main(){
scanf("%lld%lld",&n,&p);
for(int i=1;i<=n;i++)
{
if(i==1) printf("1\n");
else printf("%d\n",mod_pow(i,p-2,p));
}
return 0;
}
|
线性递推
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=3e6+5;
ll p;
ll n;
int a[MAX_N];
int main(){
scanf("%lld%lld",&n,&p);
a[1]=1;
for(int i=1;i<=n;i++)
{
if(i!=1)a[i]=(p-p/i)*a[p%i]%p;
printf("%d\n",a[i]);
}
return 0;
}
|