1. 题目
2. 读题(需要重点注意的东西)
思路:
快速幂的作用
快速地求出a的k次方模上p的结果快速幂的主要思想
预处理出logk个数,然后用这logk个数中的若干个数在O(1)的时间组合出a的k次方模上p的结果。
快速幂的证明
同余式
设有正整数m,a,b。若满足m|(a-b),即m能被(a-b)整除,则称a与b对m同余。记为:
a ≡ b (mod p) ,也可以记为 a = b + kp费马小定理
如果p是一个质数,而整数a不是p的倍数,则有a^(p-1) ≡ 1 (mod p)乘法逆元的定义(太长不看)
若整数 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,使得b × x ≡ 1 (mod m),这个x,则称 x 为 b 的模 m 的乘法逆元。
因此,求逆元就等同于求b的p-2次方模上m的结果,即快速幂。
3. 解法
---------------------------------------------------解法---------------------------------------------------
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL qmi(int a, int b, int p)
{
LL res = 1;
while (b)
{
if (b & 1) res = res * a % p;
a = a * (LL)a % p;
b >>= 1;
}
return res;
}
int main()
{
int n;
scanf("%d", &n);
while (n -- )
{
int a, p;
scanf("%d%d", &a, &p);
if (a % p == 0) puts("impossible");
else printf("%lld\n", qmi(a, p - 2, p));
}
return 0;
}
4. 可能有帮助的前置习题
5. 所用到的数据结构与算法思想
- 快速幂
6. 总结
快速幂求逆元模板题,理解公式并背下代码。
因此,求逆元就等同于求b的p-2次方模上m的结果,即快速幂,然后这个结论来得出a模p的逆元也是如此吗
多谢 同余式概念QAQ, 搞了老半天 以为是等号!!