3185056_re.cpp

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

#include <stdio.h>

int min(int a,int b)
{
	return a < b ? a : b;
}

void report(int b)
{
	while(b)
		puts("i love shengqi");
}

int gcd(int a,int b)
{
	return b==0 ? a : gcd(b,a%b);
}

int ceil(int a,int b)
{
	report(b==0);
	return a / b + (a % b != 0);
}

int floor(int a,int b)
{
	report(b==0);
	return a / b;
}



int extend_gcd(int a,int b,int &x,int &y)
{
	if(b == 0)
	{
		x = 1;
		y = 0;
		return a;
	}
	else
	{
		int gcd = extend_gcd(b,a%b,x,y);
		int t = x;
		x = y;
		y = t - (a/b)*y;
		return gcd;
	}
}

int solve(int L,int R,int D,int M)
{
	int k = floor(L,D);
	int a = ceil(L,D);
	int b = floor(R,D);

	if(a <= b)
		return a;
	else
	{
		int LL, RR, DD, MM;

		report(D==0);
		MM = D;
		DD = D - M%D;
		LL = L%D;RR = R%D;
		// Dx = Dk + D′x′ mod D.
		int xx = solve(LL,RR,DD,MM);
		
		int t = (D*k+DD*xx)%D;
		//here Dx % M = t;
		int x, y;
		int d = extend_gcd(D,M,x,y);
		report(d==0||M==0);
		int e = x*(t/d)%M;
		int ans = 2100000000;
		for(int i = 0; i < d; i++)
		{
			int tt = (e+i*M/d)%M;
			if(tt < 0)
			{
				tt += M;
			}
			if(tt < ans)
				ans = tt;
		}
		/*for(x = 0; ; x++)
		{
			if((x*D)%M==t)
				return x;
		}*/
		return ans;
	}
}

int main()
{
	int L, R, M, D;
	int cas, g;

	scanf("%d",&cas);
	while(cas-- > 0)
	{
		scanf("%d%d%d%d",&M,&D,&L,&R);
		if(L > min(R,M-1))
		{
			puts("-1");
			continue;
		}
		g = gcd(M,D);
		if(R-L+1 < g)
		{
			report(g==0);
			int tmp = g*(L/g);
			if(tmp < L && tmp + g > R)
			{
				puts("-1");
				continue;
			}	
		}
		printf("%d\n",solve(L,R,D,M));
	}
	return 0;
}