【HDU】3579 - Hello Kiki（CRT）

点击打开题目

Hello Kiki

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3262 Accepted Submission(s): 1208

Problem Description

One day I was shopping in the supermarket. There was a cashier counting coins seriously when a little kid running and singing "门前大桥下游过一群鸭，快来快来 数一数，二四六七八". And then the cashier put the counted coins back morosely and count again... Hello Kiki is such a lovely girl that she loves doing counting in a different way. For example, when she is counting X coins, she count them N times. Each time she divide the coins into several same sized groups and write down the group size Mi and the number of the remaining coins Ai on her note. One day Kiki's father found her note and he wanted to know how much coins Kiki was counting.

Input

The first line is T indicating the number of test cases. Each case contains N on the first line, Mi(1 <= i <= N) on the second line, and corresponding Ai(1 <= i <= N) on the third line. All numbers in the input and output are integers. 1 <= T <= 100, 1 <= N <= 6, 1 <= Mi <= 50, 0 <= Ai < Mi

Output

For each case output the least positive integer X which Kiki was counting in the sample output format. If there is no solution then output -1.

Sample Input

   2
2
14 57
5 56
5
19 54 40 24 80
11 2 36 20 76

Sample Output

   Case 1: 341
Case 2: 5996

Author

digiter (Special Thanks echo)

Source

2010 ACM-ICPC Multi-University Training Contest（14）——Host by BJTU

还是中国剩余定理的题，套用模板就行了。（以前我向来反对记模板，然而一个中国剩余定理给我弄的不得不记模板了，可怜 QAQ）

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define MAX 10
__int64 a[MAX+11];
__int64 m[MAX+11];
__int64 lcm;
__int64 GCD(__int64 a , __int64 b)
{
	return b == 0 ? a : GCD(b,a%b);
}
__int64 exGCD(__int64 a,__int64 b,__int64 &x,__int64 &y)
{
	if (!b)
	{
		x = 1;
		y = 0;
		return a;
	}
	int g = exGCD(b,a%b,y,x);
	y -= a / b * x;
	return g;
}
__int64 CRT(__int64 *m,__int64 *a,int n)	//x % m == a
{
	lcm = 1;
	for (int i = 1 ; i <= n ; i++)
		lcm = m[i] / GCD(m[i],lcm) * lcm;
	for (int i = 2 ; i <= n ; i++)
	{
		__int64 A = m[1] , B = m[i],d,x,y,c = a[i] - a[1];		//d 为 GCD(A,B) 
		d = exGCD(A,B,x,y);
		if (c % d != 0)		//无解 
			return -1;
		__int64 mod = m[i] / d;
		//然后套公式
		__int64 K = ((x * c / d) % mod + mod) % mod;
		a[1] = m[1] * K + a[1];
		m[1] = m[1] * m[i] / d;
	}
	if (a[1] == 0)		//如果最后合并的结果的余数为0，答案就是他们的最小公倍数 
		return lcm;
	return a[1];
}
int main()
{
	int n;
	int u;
	int Case = 1;
	scanf ("%d",&u);
	while (u--)
	{
		scanf ("%d",&n);
		for (int i = 1 ; i <= n ; i++)
			scanf ("%I64d",&m[i]);
		for (int i = 1 ; i <= n ; i++)
			scanf ("%I64d",&a[i]);
		__int64 ans = CRT(m,a,n);
		printf ("Case %d: %I64d\n",Case++,ans);
	}
	return 0;
}