AcWing 878. 线性同余方程
原题链接
简单
作者:
kRYST4L
,
2023-05-26 17:58:45
,
所有人可见
,
阅读 24
推导过程
- $ax \equiv b(mod\;m)$就可以推出$ax =my+b$
- 变形一下$ax-my =b$,不就是系数为a和-m的扩欧算法吗,即exgcd(a,-m,x,y)
- 怎么判断有没有解呢,根据裴蜀定理ax+my所能构造的最小正整数就是gcd(a,m),即$ax+my=gcd(a,m)$
- 那么要有解的情况下,b必须是gcd(a,m)的倍数,即$b\%gcd(a,m)=0$
- 由于exgcd(a,m,x,y)求得的x只是ax+my=gcd(a,m)的解
- 要求得ax+my=b的解,直接将x乘以b/gcd(a,m)的倍数即可,即$x^{\prime}=x\times \frac{b}{gcd(a,m)}$
- 最后一定要转换为longlong,防止爆int,并且要转换到int范围里,取余m即可
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int n;
int exgcd(int a,int b,int &x,int &y)
{
if(!b)
{
x=1,y=0;
return a;
}
int g=exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
return g;
}
int main()
{
cin>>n;
while (n -- )
{
int a,b,m,x,y;
cin>>a>>b>>m;
int d=exgcd(a,-m,x,y);//这里求出来的x只是ax+my=gcd(a,m)的x,要求得ax+my=b;方程两边都扩大b/gcd(a,m)倍
if(b%d!=0) cout<<"impossible"<<endl;
else cout<<(LL)x*(b/d)%m<<endl;//放在m的解系中
}
}