快速幂求逆元

• 题目：给定n组ai,pi，其中pi是质数,求ai模pi的乘法逆元，若逆元不存在则输出impossible。

  （加竖线的符号是“>”）

• 背景：乘法逆元的定义：若整数b,m互质，并且对于任意的整数a，如果满足b|a则存在一个整数x，使得a/b = a*x(mod m),则称x是b的模m乘法逆元。记为b^(-1)(mod m)。b存在乘法逆元的充要条件是b与模数m互质，当模数m为质数时，b^(m-2)就是b的乘法逆元。

• 所以：x满足a/b和a*x(mod m)有相同的余数。只需求b^(m-2)。

• 解题代码如下：

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long LL;

//求(a^p-2)%p的快速幂
 LL quickmid(int a,int b,int p)
 {int res=1;
     while(b)
     {
         if(b&1)
         res=(LL)res*a%p;
         b>>=1;
         a=(LL)a*a%p;
     }
     return res;

 }


int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,p;
        scanf("%d%d",&a,&p);
        int res=quickmid(a,p-2,p);
        if(a%p)printf("%d\n",res);//当a=2,p=2,输出impossible
    else printf("impossible\n");
        
    }
}

Donate