202503021809 数论 快速幂

快速幂

快速求 a^b % p 类似于完全背包二进制优化方法,b可以转换为二进制数相加 假如 b = 6----110, 整个数就是 a^(2^2) * a^(2^1)

可以通过先求出 元算子, 然后根据算子来求结果, 会优化很多。

因为 a^i = (a^(i - 1)) ^2 故只需要用 a = a*a%p 便可以求出所有算子

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

快速幂求逆元

根据费马定理, b 的逆元就是 b^(p - 2), 故直接用快速幂求得。

当不成立时是, b 和 m 不互质。

int main()
{
	cin >> n;
	while(n--)
	{
		int b,p;
		scanf("%d%d", &b, &p);
		int res = qmi(b, p - 2, p);
		if(b % p) cout << res << endl;
		else cout << "impossible" << endl; 
	}
	return 0;
}

题目	简介