快速幂

快速幂

快速幂的核心思想即为，将幂指数变成二进制的形式，来拆解乘积，减少运算的次数，既预处理又能防止溢出。
模板题：
https://www.acwing.com/problem/content/submission/code_detail/14148818/

#include<bits/stdc++.h>
using namespace std;
int qkm(int a,int b,int p)
{
    int res =1;
    while(b)
    {
        if(b&1) res =(long long)res*a%p;
        b>>=1;
        a=(long long)a*a%p;
    }
    return res;
    
}
int main(void)
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int a,b,p;
        scanf("%d%d%d",&a,&b,&p);
        printf("%d\n",qkm(a,b,p));
    }
}

快速幂求逆元

基础知识：

费马小定理：
p为质数，且a，p互质则。
a^p=1(modp)
欧拉定理：
对任意互素的a，n，有
a^phi(n) =1 (mod n)
费马小定理为欧拉定义的特殊情况。
由此可以推出乘法逆元的充要条件。

模板：
https://www.acwing.com/problem/content/878/

#include<bits/stdc++.h>
using namespace std;
int qkm(int a,int b,int p)
{
    int res =1;
    while(b)
    {
        if(b&1) res =(long long)res*a%p;
        b>>=1;
        a=(long long)a*a%p;
    }
    return res;
    
}
int main(void)
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int a,p;
        scanf("%d%d",&a,&p);
        int res = qkm(a,p-2,p);
        if(a%p!=0) printf("%d\n",res);
        else printf("impossible\n");
    }
}