AcWing 876. 快速幂求逆元

题目链接

https://www.acwing.com/problem/content/878/

思路

通过费马小定理可以计算当a和p互质的情况，由于题目说明了p一定是质数，那么我们只用关系a是否是p的倍数即可，如果是p的倍数，那么我们就不能求得逆元，否则我们可以通过快速幂求得逆元

代码

#include
using namespace std;

#define ll long long

ll ksm(ll a,ll b,ll p){
    ll res = 1LL;
    for(;b;b>>=1,a = a*a % p) if(b&1) res = res * a % p;
    return res;
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1;i