快速幂模板
给定 n 组 ai,bi,pi对于每组数据,求出 ai ^ bi mod pi 的值。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含三个整数 ai,bi,pi。
输出格式
对于每组数据,输出一个结果,表示 ai ^ bi mod pi 的值。
每个结果占一行。
数据范围
1≤n≤100000
1≤ai,bi,pi≤2×10^9
输入样例:
2
3 2 5
4 3 9
输出样例:
4
1
代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL qmi(int a, int b, int p)
{
LL res = 1 % p;
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, b, p;
scanf("%d%d%d", &a, &b, &p);
printf("%lld\n", qmi(a, b, p));
}
return 0;
}
快速幂求逆元
给定 n 组 ai,pi,其中 pi 是质数,求 ai 模 pi 的乘法逆元,若逆元不存在则输出 impossible
。
注意:请返回在 0∼p−1 之间的逆元。
乘法逆元的定义
若整数 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 的乘法逆元。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一个数组 ai,pi,数据保证 pi 是质数。
输出格式
输出共 n 行,每组数据输出一个结果,每个结果占一行。
若 ai 模 pi 的乘法逆元存在,则输出一个整数,表示逆元,否则输出 impossible
。
数据范围
1≤n≤10^5
1≤ai,pi≤2∗10^9
输入样例:
3
4 3
8 5
6 3
输出样例:
1
2
impossible
逆元
在取模操作中,逆元是指在模 n 的情况下,对于一个整数 a(且 a 和 n 互质),存在一个整数 b,使得 a ⋅ b ≡ 1 mod n。这个 b 被称为 a 的模逆元。求模逆元通常可以使用扩展欧几里得算法。
假设我们要计算 3 / 5 mod 7那么就是要计算5的逆元
费马小定理
代码
#include <iostream>
using namespace std;
typedef long long ll;
int t;
ll a,p;
ll qmi(ll m, ll k, ll p)
{
ll res = 1 % p, t = m;
while (k)
{
if (k&1) res = res * t % p;
t = t * t % p;
k >>= 1;
}
return res;
}
ll inv(ll a,ll p)
{
return qmi(a,p - 2,p);
}
void solve()
{
cin >> a >> p;
if(a % p == 0) cout << "impossible" << endl;
else cout << inv(a,p) << endl;
}
int main()
{
cin >> t;
while(t --){
solve();
}
return 0;
}
加油
标签:幂求,ai,res,ll,int,逆元,pi,快速 From: https://blog.csdn.net/AuRoRamth/article/details/143193289