3238069_re.cpp

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

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

using namespace std;

int n;
struct node
{
	__int64 a, r;
};

vector <node> num;

__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 lcm(__int64 a,__int64 b)
{
	__int64 x, y;

	return a*b/extend_gcd(a,b,x,y);
}

int main()
{
	int i;
	node t;
	__int64 A1, A2, B1, B2;

	while(scanf("%d",&n)==1)
	{
		num.clear();
		for(i = 0; i < n; i++)
		{
			scanf("%I64d%I64d",&t.a,&t.r);
			num.push_back(t);
		}
		for(i = 1; i < num.size(); i++)
		{
			A1 = num[i-1].r;B1 = num[i-1].a;
			A2 = num[i].r;B2 = num[i].a;
			if(A2 < A1)
			{
				swap(A2,A1);
				swap(B2,B1);
			}
			//here Dx % M = t;
			//X1B1 % B2 ≡ A2-A1
			__int64 D = B1, M = B2, t = A2-A1;
			__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;
			}
			__int64 C, B;
			C = A1+ans*B1;
			B = lcm(B1,B2);
			num[i].a = C;
			num[i].r = B;
		}
		printf("%I64d\n",num[n-1].a);
	}
	return 0;
}