快速幂求逆元
//为了解决什么问题? 为了解决大数的除法,避免高精度计算。
//举个例子:6 / 3 % 5 = 2,那么我们可以找到一个逆元t,使得6*t%5=2,比如当t=2就可以做到。
//如何求解逆元? 当b和p互质的时候,关于b,p的逆元等于qmi(b,p-2,p);
//由于太笨辣,不会写证明,所以就记住就好了
//判断两个数是不是互质的代码
// bool isCoprime(int x,int y)
// {
// if(x==1 && y==1)//1和1互质
// return true;
// else if(x<=0 || y<=0 || x==y)//非正整数都不存在互质的说法
// return false;
// else if(x==1 || y==1)//1和任何正整数都互质
// return true;
// else
// {
// int tmp=0;
// //使用求商判断法,如果输入的x<y,第一次循环会交换x和y的位置
// while(true)
// {
// tmp=x%y;
// if(tmp==0)
// {
// break;
// }
// else
// {
// x=y;
// y=tmp;
// }
// }
// if(y==1) //最大公约数为1,所以互质
// return true;
// else //最大公约数大于1,所以不互质
// return false;
// }
// }
//辗转相除法判断两个数是否互质;
// int zhanzhuan(int a, int b)
// {
// return b ? zhanzhuan(b, a % b) : a;
// }
#include<iostream>
using namespace std;
typedef long long LL;
int 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;
cin>>n;
while(n--)
{
int a,p;
cin>>a>>p;
// if(!isCoprime(a,p)) puts("impossible");
// if(zhanzhuan(a,p)>1) puts("impossible");
if(a%p==0) puts("impossible");//由于本题指出p是质数,所以只要判断a,p是不是有除一以外的公约数,也即是p本身。
else cout<<qmi(a,p-2,p)<<endl;
}
return 0;
}
www 我的数论什么都不会qwq
哈哈,我也啥都不会,我不仅数论不会,而且dp也不会
qwq 我现在已经沦落到只能听懂数据结构的境地了呜呜呜
费马小定理只适用于p是素数