简单记一下
题目:ax≡b(mod m)求x
转化:
$$ax≡(b+ym)(mod\ m)$$
$$ ax-my≡b(mod\ m)$$
$$令y^{‘}=-y,有ax+my^{‘}≡b(mod\ m)$$
根据裴蜀定理,当且仅当b是gcd(a,m)的倍数时,x才存在。
所以我们可以利用exgcd(a,m)求出下式的x,y:
$$ax+my=gcd(a,m)(mod\ m)$$
把求出的x记作x'
,这个x’不是题目所求x,题解还要乘以一个倍数:
$$x_{题解}=(x’ \times \frac{b}{gcd(a,m)} )\ mod\ m$$
但是我们需要注意,这里求出的一组x,y
仅仅是一组特解
,若有解则解有无穷多个。
如何求通解
参考https://www.acwing.com/file_system/file/content/whole/index/content/444031/
代码
#include<iostream>
using namespace std;
#include<algorithm>
typedef long l;
typedef pair<l,l> II;
l gcd;//gcd为最大公约数
II exgcd(l a,l b){
if(b==0){
gcd=a;//当b为0时,a就是最大公约数
return {1,0};
}
else{
II temp=exgcd(b,a%b);
return {temp.second,temp.first-a/b*temp.second};
}
}
int main(void){
l n,a,b,m;
cin>>n;
while(n--){
cin>>a>>b>>m;
II temp;
temp=exgcd(a,m);
if(b%gcd==0) cout<<(temp.first*(b/gcd))%m<<endl;//若b是a,m最大公约数的倍数,有解
else cout<<"impossible"<<endl;
}
}