3186595_wa.cpp

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

#include <stdio.h>

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

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

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

int floor(int a,int b)
{
	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)
{
	if(R > M - 1)
		R = M-1;
	if(D > M)
	{
		D %= M;
	}
	if(D > M-D)
	{
		D = M-D;
		int tl = L;
		L = M-R;
		R = M-tl;
	}
	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;

		MM = D;
		DD = D - M%D;
		LL = L%D;RR = R%D;
		int xx = solve(LL,RR,DD,MM);
		int t = D*k+(DD*xx)%D;
		int x, y;
		int d = extend_gcd(D,M,x,y);
		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;
		}
		return ans;
	}
}

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

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