写出不定方程后,不就是得到一个同余方程吗,为什么不能按照有理数取余来做呢?
#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL gcd(LL a, LL b){
return b == 0? a :gcd(b, a%b);
}
pair<LL , LL> exgcd(LL a, LL b){
if(b == 0) return {1, 0};
auto [x, y] = exgcd(b , a % b);
return {y, x - y* (a / b)};
}
int main(){
LL x, y, m, n, L, b, a;
cin >>x >>y >>m >>n >>L;
b = m - n, a = y - x;
if( b < 0){
b = -b;
a = -a;
}
a %= L, b %= L;
if( a%gcd(b, L)!=1 ) cout<<"Impossible\n";
auto [x1, y1] = exgcd(b, L);
x1 = (x1 % L + L)% L;
cout<< ((a * x1) % L + L)% L;
return 0;
}