算法基础之快速幂求逆元

快速幂求逆元

• 核心思想： 逆元：

  • 逆元 == a^p-2 mod p

  •   #include<iostream>
      #include<algorithm>
      
      using namespace std;
      typedef long long LL;
      
      LL pmi(int a,int b,int c)
      {
          LL res = 1;
          while(b)
          {
              if(b & 1) res = res * a %c;
              b >>= 1;
              a = (LL) a * a %c;
          }
          
          return res;
      }
      
      int main()
      {
          int n;
          cin>>n;
          while(n--)
          {
              int a,b;
              cin>>a>>b;
              if(a % b) cout<<pmi(a,b-2,b)<<endl;  //若a%b ==0 说明不存在逆元
              else puts("impossible");
          }
      }