求逆元

费马小定理

#include<cstdio>
#include<cstring>
using namespace std;
int Quick_Power(int a,int b,int c)
{
    int ans=1;
    while(b)
    {
        if(b&1)
          ans=(1ll*ans*a)%c;
        a=(1ll*a*a)%c;
        b>>=1;
    }
    return ans;
}
int main()
{
    int a,b,p;
    scanf("%d%d%d",&a,&b,&p);
    b=Quick_Power(b,p-2,p);
    printf("%d",((a%p)*(b%p))%p);
    return 0;
}

扩展欧几里得

#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
void extgcd(ll a,ll b,ll& d,ll& x,ll& y){
    if(!b){ d=a; x=1; y=0;}
    else{ extgcd(b,a%b,d,y,x); y-=x*(a/b); }
}
ll inverse(ll a,ll n){
    ll d,x,y;
    extgcd(a,n,d,x,y);
    return d==1?(x+n)%n:-1;
}
int main(){
    ll a,m;
    cin>>a>>m;
    cout<<inverse(a,m);
}

筛法

#include<cstdio>
#include<cstring>
#define N 1000005
using namespace std;
int inv[N];
void get_inverse(int n,int p)
{
    int i;
    inv[1]=1;
    for(i=2;i<=n;++i)
      inv[i]=(p-p/i)*inv[p%i]%p;
}
int main()
{
    int n,i,p;
    scanf("%d%d",&n,&p);
    get_inverse(n,p);
    return 0;
}