数学知识下

线性同余方程

#include <bits/stdc++.h>
using namespace std;
int n;
typedef long long LL;
LL a,b,m;
LL x,y;


LL gcd(LL a,LL b){
    return b==0?a:gcd(b,a%b);
}

// ax = b mod m
// ax + my = b

LL exgcd(LL a,LL b,LL& x,LL &y){
    if(b==0){
        x=1;y=0;
        return a;
    }
    LL r = exgcd(b,a%b,y,x);
    y-=a/b*x;
    return r;
}


int main(){
    cin>>n;
    for(int i =1;i<=n;i++){
        cin>>a>>b>>m;
        if(b%gcd(a,m)==0){
            LL r = exgcd(a,m,x,y);
            cout<<(b/r*x+m)%m<<endl;
        }else puts("impossible");
    }
    return 0;
}

中国剩余定理：

...互质的话

...

如果不互质
就要使用扩展欧几里得