chinese remainder theorem again(数论).cpp

来自「杭电acm解题报告2001---2099.」· C++ 代码 · 共 34 行

//N = Mi - a (mod Mi)
//N + a = Mi (mod Mi)
//N = LCM(Mi) - a
#include <cstdio>

__int64 GCD(__int64 x, __int64 y)
{
	__int64 t;
	while(y > 0) {
		t = x % y;
		x = y;
		y = t;
	}
	return x;
}


int main()
{
	int j,i,a,m;
	__int64 lcm;
	while (scanf("%d %d",&i,&a)==2) {
		if (i==0 && a==0) {
			break;
		}
		scanf("%I64d",&lcm);
		for (j=1;j<i;j++) {
			scanf("%d",&m);
			lcm = lcm * m / GCD(lcm, m);
		}
		printf("%I64d\n",lcm - a);
	}
}