3185205_mle.cpp

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

#include <stdio.h>
#include <stack>
#include <algorithm>

using namespace std;

struct node
{
	int L, R, D, M;
	int a, b, k;
};

stack <node> stk;

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 ll,int rr,int dd,int mm)
{
	node tmp, in, last;
	int t, d, e;
	int x, y, ret;
	int L, D, M, R;
	bool mark;

	mark = false;
	while(!stk.empty())
		stk.pop();
	tmp.L = ll;tmp.D = dd;
	tmp.M = mm;tmp.R = rr;
	tmp.a = ceil(ll,dd);
	tmp.b = floor(rr,dd);
	tmp.k = floor(ll,dd);
	stk.push(tmp);
	while(!stk.empty())
	{
		tmp = stk.top();
		L = tmp.L;R = tmp.R;
		D = tmp.D;M = tmp.M;
		if(mark)
		{
			t = (D*tmp.k+last.D*ret)%D;
			d = extend_gcd(D,M,x,y);
			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;
			}
			ret = ans;
			last = tmp;
			stk.pop();
		}
		else
		{
			if(tmp.a<=tmp.b)
			{
				mark = true;
				ret = tmp.k;
				last = tmp;
				stk.pop();
			}
			else
			{
				in.M = D;
				in.D = D-M%D;
				in.L = L%D;
				in.R = R%D;
				in.a = ceil(in.L,in.D);
				in.b = floor(in.R,in.D);
				in.k = floor(in.L,in.D);
				stk.push(in);
			}
		}
	}
	return ret;
}

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