中国剩余定理（SCAUOJ 1077）

1077 韩信点兵

时间限制:500MS 内存限制:65536K
提交次数:1103 通过次数:99

题型: 编程题语言: 无限制

Description

相传汉高祖刘邦问大将军韩信统御兵士多少，韩信答说，每3人一列余1人、5人一列余2人、7人一列余4人、13人一列余6人、17人一列余2人、19人一列余10人、23人一列余1人、29人一列余11人。

刘邦茫然而不知其数。你呢？你是一位优秀的程序员，请你帮刘邦解决这一问题。

输入格式

要求由键盘输入A,B,C,D,E,F,G,H,a,b,c,d,e,f,g,h十六个数，分别代表每A人一列余a、每B人一列余b、每C人一列余c、每D人一列余D、每E人一列余e、每F人一列余f、每G人一列余g、每H人一列余h，其中A,B,C,D,E,F,G,H为互不相等的质数

输出格式

输出总兵士数，要求输出满足条件的最小的一个，但要满足8种排法的每一种排法至少可排一列。（保证给的数据，有结果且计算的结果不会超过2的63次方）

输入样例

2 3 5 7 11 13 17 19
1 1 1 1 1 1 1 1

输出样例

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <iostream>
 5 
 6 using namespace  std;
 7 
 8 typedef long long LL;
 9 void gcd(LL a, LL b, LL &d, LL &x, LL &y) {
10     if (b) { gcd(b, a % b, d, y, x); y -= a / b * x;}
11     else { d = a, x = 1, y = 0;}
12 }
13 
14 LL inv(LL a, LL m) {
15     LL x, y, d;
16     gcd(a, m, d, x, y);
17     return d == 1 ? (x + m) % m : -1;
18 }
19 
20 LL a[10], b[10];
21 
22 bool input() {
23     for (int i = 0; i < 8; i++) {
24         if (!(cin >> a[i])) return false;
25     }
26     for (int i = 0; i < 8; i++) {
27         if (!(cin >> b[i])) return false;
28     }
29     return true;
30 }
31 
32 LL work() {
33     LL x, y, d, ret = 0, M = 1, mx = 0;
34     for (int i = 0; i < 8; i++) M *= a[i];
35     //cout << M << endl;
36     for (int i = 0; i < 8; i++) {
37         mx = max(mx, a[i]);
38         gcd(M / a[i], a[i], d, x, y);
39         //cout << x << ' ' << y << endl;
40         if (b[i] % d) return -1;
41         ret += M / a[i] * x * b[i];
42         ret %= M;
43     }
44     ret %= M;
45     while (ret < mx) ret += M;
46     return ret;
47 }
48 
49 int main() {
50     //freopen("in", "r", stdin);
51     while (input()) {
52         cout << work() << endl;
53     }
54     return 0;
55 }

View Code

——written by Lyon