3186592_ac_0ms_148k.cpp

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

#include <stdio.h>

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

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

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

__int64 floor(__int64 a,__int64 b)
{
	return a / b;
}

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

__int64 solve(__int64 L,__int64 R,__int64 D,__int64 M)
{
	if(R > M - 1)
		R = M-1;
	if(D > M)
	{
		D %= M;
	}
	if(D > M-D)
	{
		D = M-D;
		__int64 tl = L;
		L = M-R;
		R = M-tl;
	}
	__int64 k = floor(L,D);
	__int64 a = ceil(L,D);
	__int64 b = floor(R,D);

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

		MM = D;
		DD = D - M%D;
		LL = L%D;RR = R%D;
		// Dx = Dk + D′x′ mod D.
		__int64 xx = solve(LL,RR,DD,MM);
		__int64 t = D*k+(DD*xx)%D;
		//here Dx % M = t;
		__int64 x, y;
		__int64 d = extend_gcd(D,M,x,y);
		__int64 e = x*(t/d)%M;
		__int64 ans = 2100000000000;
		for(__int64 i = 0; i < d; i++)
		{
			__int64 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()
{
	__int64 L, R, M, D, g;
	int cas;

	scanf("%d",&cas);
	while(cas-- > 0)
	{
		scanf("%I64d%I64d%I64d%I64d",&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)
		{
			__int64 tmp = g*(L/g);
			if(tmp < L && tmp + g > R)
			{
				puts("-1");
				continue;
			}
		}
		printf("%I64d\n",solve(L,R,D,M));
	}
	return 0;
}