x+km≡y+kn(modl)
k(m−n)≡y−x(modl)
k(m−n)+kk⋅l=y−x (kk为常数)
然后求出 (m−n) 与 l 的最大公因数,以及k(m−n)+kk⋅l=gcd(m−n,l) 中的 x,y 的值,然后判断 (y−x) 和 gcd(m−n,l) 是否有倍数关系,有则输出 k,否则输出“Impossible”
code:
#include<bits/stdc++.h>
using namespace std;
struct p
{
long long x,y,GCD;
};
p exgcd(long long a,long long b)
{
if(b==0)
{
p M;
M.x=1,M.y=0,M.GCD=a;
return M;
}
p M=exgcd(b,a%b);
p ans;
ans.x=M.y,ans.y=M.x-a/b*M.y,ans.GCD=M.GCD;
return ans;
}
int main()
{
long long x,y,m,n,l;
cin>>x>>y>>m>>n>>l;
long long a=y-x,b=m-n;
b=(b%l+l)%l;
a=(a%l+l)%l;
p yuhaohanhan=exgcd(b,l);
if(yuhaohanhan.GCD%a==0||a%yuhaohanhan.GCD==0)
cout<<(yuhaohanhan.x%l+l)%l;
else
cout<<"Impossible";
return 0;
}
求助qwq