1905425_ac_15ms_168k.cc

北大大牛代码 1240道题的原代码 超级权威

# include <iostream>
using namespace std;

long long exgcd(long long m,long long & x,long long n,long long & y)  // Extend Euclid 
{	long long x1,y1,x0,y0;
	x0=1;y0=0;
	x1=0;y1=1;
          long long r=(m%n+n)%n;
	long long q=(m-r)/n;
	x=0;y=1;
	while(r)
	{  x=x0-q*x1;y=y0-q*y1; x0=x1;y0=y1;
	    x1=x;y1=y;
	    m=n;n=r;r=m%n;
	   q=(m-r)/n;
	}
	return n;
}
int main()
{	long long r,t;
	long long x,y,m,n,l;

	cin>>x>>y>>m>>n>>l;
	long long ar,br;
	long long M=exgcd(n-m,ar,l,br);
	if((x-y)%M||m==n)
		cout<<"Impossible"<<endl;
	else
	{  long long s=l/M;
	    ar=ar*((x-y)/M);
	    ar=(ar%s+s)%s;
	    cout<<ar<<endl;
	}
	return 0;
}