求逆元的三种方法（模板）

#include <bits/stdc++.h>
 
#define maxn 2000050
#define inf 0x3f3f3f3f
#define debug(a) cout << #a << ": " << a << endl
#define false_stdio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define pi acos(-1.0)
typedef long long ll;
using namespace std;
 
const ll mod=1e9+7;

ll inv[maxn];

//扩展欧几里得
void exgcd(ll a, ll b, ll &x, ll &y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return;
	}
	exgcd(b, a%b, y, x);
	y -= a / b * x;
}

//二进制快速幂
ll pow2(ll base, ll sup) {
	ll sum = 1;
	while(sup) {
		if (sup & 1)sum = sum * base%mod;
		sup >>= 1;
		base = base * base%mod;
	}
	return sum;
}

//a是要求的数，p是模数
ll solve(ll a,ll p) {
	
    //扩展欧几里得求逆元
    // ll x, y; 
    //exgcd(a, p, x, y); 
    // return x;

    //费马小定理求逆元
    //return pow2(a, mod - 2);//二进制快速幂

    //逆元递推，要求p为奇质数
    // inv[1]=1;
    // for(int i=2;i<=x;i++){
    //     inv[i]=1ll*(p-p/i)*inv[p%i]%p;
    // }
    // return inv[x];
}

int  main() {
	false_stdio;
	
	return 0;
}