算法基础之快速幂求逆元

2023-12-21 23:50:31

快速幂求逆元

  • 核心思想: 逆元:在这里插入图片描述

    • 逆元 == ap-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");
            }
        }
      

文章来源:https://blog.csdn.net/Pisasama/article/details/135142222
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。