
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