3238818_wa.cpp

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

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

using namespace std;

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

vector <node> num;

__int64 mod(__int64 a,__int64 b)
{
	if(a >= 0)
      return a % b;
	else
      return a % b + b;
}

__int64 gcd(__int64 a,__int64 b)
{
	if(b == 0)
		return a;
	else
		return gcd(b,mod(a,b));
}

__int64 lcm(__int64 a,__int64 b)
{
	return a*b/gcd(a,b);
}

struct triple
{
	__int64 d,x,y;
};

triple Extended_Euclid(int a,int b)
{
	triple result;
	
	if(b == 0)
	{
		result.d = a;
		result.x = 1;
		result.y = 0;
	}
	else
	{
		triple ee = Extended_Euclid(b,mod(a,b));
		result.d = ee.d;
		result.x = ee.y;
		result.y = ee.x - (a/b)*ee.y;
	}
	return result;
}

__int64 MLES(__int64 a,__int64 b,__int64 n)
{
	triple ee = Extended_Euclid(a,n);
	
	if(mod(b,ee.d) == 0)
		return mod((ee.x * (b / ee.d)),n / ee.d);
	else
		return -1;
}

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(B1==B2)
			{
				continue;
			}
			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 ans = MLES(D,t,M);
			__int64 C, B;
			C = A1+ans*B1;
			B = lcm(B1,B2);
			num[i].a = B;
			num[i].r = C;
		}
		printf("%I64d\n",num[n-1].r);
	}
	return 0;
}