#快速幂 ——快速幂求逆元 ~20.8.28

快速幂

题 目：快速幂

AcWing 875. 快速幂
给定n组ai,bi,pi，对于每组数据，求出a^bi_i mod p_i的值。

输入格式
第一行包含整数n。

接下来n行，每行包含三个整数a_i,b_i,p_i。

输出格式
对于每组数据，输出一个结果，表示a^bi_i mod p_i的值。

每个结果占一行。

数据范围
1≤n≤100000,
1≤a_i,b_i,p_i≤2∗10⁹
输入样例：
2
3 2 5
4 3 9
输出样例：
4
1

思路：反复平方法

将k拆分成若干个2的n次方相加的形式，并用预处理好的a^2的0次方 ~2的logk次方^{进行组合相乘得到a}k^。
第一步、预处理出 a^2的0次方 ~2的logk次方^ mod P的结果，一共logk个。
预处理时，a^2的k次方= a^{2的(k-1)次方}* a^{2的(k-1)次方}= a^{2的(k-1)次方}的平方
第二步、将a^k组合出来

int qmi(int a, int k, int p){
    int res = 1;
    while(k){
        if(k & 1) res = (ll)res * a % p;//如果k的二进制位有1那么就乘上当前的a
        k >>= 1;//k向右移一位
        a = (ll)a * a % p;//将a变成下一步的a
    }
    return res;
}

答案

#include<bits/stdc++.h>
using namespace std;
int n;
typedef long long ll;
int qmi(int a, int k, int p){
    int res = 1;
    while(k){
        if(k & 1) res = (ll)res * a % p;
        k >>= 1;
        a = (ll)a * a % p;
    }
    return res;
}
int main(){
    cin >> n;
    while(n --){
        int a, k, p;
        cin >> a >> k >> p;
        cout << qmi(a, k, p) << endl;
    }
    return 0;
}

题 目：快速幂求逆元

AcWing 876. 快速幂求逆元
给定n组a_i,p_i，其中p_i是质数,求a_i模p_i的乘法逆元，若逆元不存在则输出impossible。

输入格式
第一行包含整数n。

接下来n行，每行包含一个数组ai,pi，数据保证pi是质数。

输出格式
输出共n行，每组数据输出一个结果，每个结果占一行。

若ai模pi的乘法逆元存在，则输出一个整数，表示逆元，否则输出impossible。

数据范围
1≤n≤105,
1≤a_i,p_i≤2∗10⁹
输入样例：
3
4 3
8 5
6 3
输出样例：
1
2
impossible

思路

……
这里输入的a是题目定义里面的b,p是定义里的m。
所以求a的逆元的话，只需满足 a，p互质，
然后根据公式 算出 a^p-2 mod p 的值就好。
.
……
总的来说，直接求 (a/b)%m可能会出错，于是想办法用一个x来代替b^-1的作用，使得(a *x)mod p同余于(a/b)%m

……辅助说明

1、转自 @无糖卡布奇诺 的文章 《逆元（关于除法取模）》

2、来自 @Dunyb 的文章 《逆元》

答案

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int qmi(int a, int k, int p){
    int res = 1;
    while(k){
        if(k & 1) res = (ll)res * a %  p;
        k >>= 1;
        a = (ll) a * a % p;
    }
    return res;
}

int main(){
    int n;
    cin >> n;
    while(n --){
        int a, p;
        cin >> a >> p;
        
        if(a % p) {//p已经是质数了，那么如果a还不能整除p，就说明它们互质
           int res = qmi(a, p - 2, p);
           cout << res << endl;
        }
        else cout << "impossible" << endl;
    }
    return 0;
}