1843891_ce.c

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

# include <stdio.h>

long exgcd(long m,long x,long n,long y)  /* Extend Euclid */
{	long x1, y1, x0, y0;
	x0 = 1;y0 = 0;
	x1 = 0;y1 = 1;
    long r = (m%n+n)%n;
	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;
}

void main()
{	
	long x,y,m,n,L;
	scanf("%ld%ld%ld%ld%ld",&x,&y,&m,&n,&L);
	long ar = x;
	long M=exgcd(n-m,x,L,y);
	if((x-y)%M||m==n)
		printf("Impossible\n");
	else
	{   
	    long s=L/M;
	    ar=ar*((x-y)/M);
	    ar=(ar%s+s)%s;
	    printf("%ld\n",ar);
	}
}