C/C++教程

快速幂求逆元（C++）

本文主要是介绍快速幂求逆元（C++），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目

 

输入样例：

3
4 3
8 5
6 3

输出样例：

1
2
impossible

代码

#include<iostream>

using namespace std;

typedef long long LL;

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;
}

int main()
{
	int n;
	cin >> n;
	
	while(n --)
	{
		int a, p;
		cin >> a >> p;
		if(a % p )
		cout << qmi(a, p - 2, p) << endl;
		else puts("impossible");
	}
	return 0;
}

这篇关于快速幂求逆元（C++）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航