线性同余方程（扩展欧几里得acwing878）

思路：

扩展欧几里得：

对于任意a,b,存在x,y使a*x+b*y=gcd(a,b);

对于a,b存在x,y使a*x+b*y=d<==>d%gcd(a,b)=0；

若d%gcd(a,b)=0,因为a*x+b*y=gcd(a,b),让方程两边同乘d/gcd(a,b)；

因为a%gcd(a,b)=0&&b%gcd(a,b)=0,则d%gcd(a,b)=0；

这题要注意两点：x*d/gcd(a,b)可能会超出int范围，所以加个longlong，因为答案要求int，我们可以对%m，不会影响答案。

代码：

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

}
int main()
{
    int a, b, x, y,m;
    scanf("%lld", &n);
    while (n--)
    {
        scanf("%d%d%d", &a, &b,&m);
        int d=exgcd(a, m, x, y);
        if (b % d!=0) printf("impossible\n");
        else
            printf("%d\n", (LL)x * b / d%m);
    }
    return 0;
}