线性同余方程(扩展欧几里得算法)

线性同余方程

给定 n 组数据 ai,bi,mi，对于每组数求出一个 xi，使其满足 $a_i * x_i≡ b_i (mod\ m_i)$，如果无解则输出 impossible。

输入格式
第一行包含整数 n。

接下来 n 行，每行包含一组数据 ai,bi,mi。

输出格式
输出共 n 行，每组数据输出一个整数表示一个满足条件的 xi，如果无解则输出 impossible。

每组数据结果占一行，结果可能不唯一，输出任意一个满足条件的结果均可。

输出答案必须在 int 范围之内。

数据范围
1≤n≤10^5,
1≤ai,bi,mi≤2×10^9
输入样例：
2
2 3 6
4 3 5
输出样例：
impossible
-3

题解

ax = b(mod m)
ax = b + ym
ax - my = b 这个式子符合裴蜀定理，ax-my的整数解为gcd(a,-m)的倍数，通过拓展欧几里得算法求出
它的一组解(x,y)和gcd(a,-m)后,判断gcd(a,-m)是否可以整除b,如果可以整除,等式两边就乘以 b/gcd(a,-m)，
得出ax-ym = b的(x,y)解

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;

/*
ax+by=d  bx+(a%b)y=d 
bx+(a-a/b*b)y=d
ay+bx-a/b*by=d
ay+b(x-a/b*y)=d

x = y
y = x-a/b*y
*/
int exgcd(int a,int b,int &x,int &y)
{
    if(b==0){
        x = 1,y = 0;
        return a;
    }
    int d = exgcd(b,a%b,y,x);
    y -= a/b*x;
    return d;
}
int main()
{
    int n;
    cin>>n;
    while (n -- ){
        int a,b,m;
        int x,y;
        cin>>a>>b>>m;
        int d = exgcd(a,-m,x,y);
        if(b%d==0){
            cout<<(LL)x*(b/d)%m<<endl;
        }
        else cout<<"impossible"<<endl;
    }
    return 0;
}