高密市赏旋网站设计有限公司_济南富库网络技术有限公司_为什么打开网址都是站长工具_谷歌关键词排名查询工具

题目一 快速幂

解题思路

1. 预处理出$a^{2^0}$, $a^{2^1}$, $a^{2^2}$, $a^{2^4}$…
2. 将这些数组合成所要求的a^b,即令a^b = $a^{2^0}$ * $a^{2^1}$ * $a^{2^2}$ * $a^{2^4}$…(b = 2⁰+2¹+ 2²+ …)将b用二进制表达;

注：

1. &的用法：& 用作按位与（AND）运算符。它比较两个数的每一位，如果两个相应的位都是1，则结果的该位为1，否则为0。在下方代码中，用b&1来判断b的二进制第一位是否为1
   一些模的性质：
2. (a + b) % p = (a % p + b % p) % p
3. (a - b) % p = (a % p - b % p) % p
4. (a * b) % p = (a % p * b % p) % p
5. a^b % p = ((a % p)^b) % p

解释了为什么在代码过程中%上一个数结果不会变

代码实现

#include<iostream>using namespace std;void qmi(int a, int b, int p)
{long long res = 1;while(b){if(b&1)//查看b的二进制第一位是否为1{res = res * a % p;}b >>= 1;//b向右进一位；a = (long long)a * a % p;//将a在循环中变成$a^{2^0}$, $a^{2^1}$, $a^{2^2}$, $a^{2^4}$... //%p防止a过大爆int}cout << res << endl;
}int main()
{int n, a, b, p;cin >> n;while(n -- ){scanf("%d%d%d", &a, &b, &p);qmi(a, b, p);}return 0;
}

题目二 快速幂求逆元

解题思路

什么是逆元：
在模运算中，如果 a 和 m是整数，且 a 和 m 互质（即 gcd⁡(a,m)=1），那么存在一个整数 b 使得 a⋅b≡1(modm)。这个 b 就是 a 在模 m 下的乘法逆元。

费马小定理：
如果 p 是一个质数，a是一个不被 p整除的整数，那么 a^p-1≡1(modp);

由a^p-1≡1(modp)得a*a^p-2≡1(modp),可得a^p-2就是a得逆元（p为质数）

1. 题目规定p为质数，则根据费马小定理和欧拉定理，可以得出所要求的逆元就是a^p-2;
2. 用快速幂求出a^p-2
3. 按照题目要求返回0~p-1之间的逆元，所以要%p；

代码实现

#include<iostream>using namespace std;long long qmi(int a, int b, int p)
{long long res = 1;while(b){if(b&1){res = res * a % p;}b >>= 1;a = (long long)a * a % p;}return res;
}int main()
{int n, a, p;cin >> n;while(n -- ){scanf("%d%d", &a, &p);long long t = qmi(a, p - 2, p);if(a % p == 0)//如果a与p不互质，则a没有0~p-1内的逆元（在qmi计算过程中有%p这一操作）{cout << "impossible" << endl;}else{cout << t << endl;        }}return 0;
}