| 编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
|---|---|---|---|---|---|---|---|---|
| #9939 | #1071. zzy数糖果 | Accepted | 100 | 43 ms | 356 K | C++ / 1.6 K | lenijwp | 2019-07-03 20:30:12 |
/*看了题解，才知道数据中有只有一组数据，并且整除的数据
if(n==1&&a[1]==0)
{
printf("Case %d: %d\n",opt,m[1]);
continue;
}只有一组数据，并且还整除，中国剩余定理是解决不了的，要特判。
*/
#include <bits/stdc++.h>
using namespace std;
#include <cstdio>
#define inf (1 << 31) - 1
#define N 10
void exgcd(int a, int b, int &x, int &y, int &gcd) {
if (b == 0) {
x = 1;
y = 0;
gcd = a;
return;
}
exgcd(b, a % b, x, y, gcd);
int t = x;
x = y;
y = t - (a / b) * y;
}
int main() {
// freopen("10.in","r",stdin);
// freopen("10.out","w",stdout);
int T;
scanf("%d", &T);
int opt = 0;
while (T--) {
++opt;
int n, m[N] = { 0 }, a[N] = { 0 };
int m1, m2, a1, a2, x, y, gcd;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d%d", &m[i], &a[i]);
m1 = m[1];
a1 = a[1];
if (n == 1 && a[1] == 0) {
printf("%d\n", m[1]);
continue;
}
bool flag = false;
for (int i = 2; i <= n; ++i) {
a2 = a[i];
m2 = m[i];
exgcd(m1, m2, x, y, gcd);
if ((a2 - a1) % gcd) {
flag = true;
break;
}
int t = m2 / gcd;
x = (x * (a2 - a1)) / gcd;
x = (x % t + t) % t;
a1 = m1 * x + a1;
m1 = (m1 * m2) / gcd;
a1 = (a1 % m1 + m1) % m1;
}
if (flag)
printf("-1\n");
else
printf("%d\n", a1);
}
return 0;
}200
1
44 22
6
28 15
12 5
8 4
6 4
10 9
27 12
1
44 35
6
41 10
46 3
16 7
15 12
39 11
<5178 bytes omitted>22
-1
35
-1
27
-1
56
-1
-1
123135
-1
-1
-1
-1
18
-1
-1
-1
-1
13
-1
-1
-1
-1
<745 bytes omitted>用户输出
22
-1
35
-1
27
-1
56
-1
-1
123135
-1
-1
-1
-1
18
-1
-1
-1
-1
13
-1
-1
-1
-1
125
-1
-1
-1
-1
305
2707
161807
-1
-1
-1
515
25
-1
-
<517 bytes omitted>系统信息
Exited with return code 0200
2
24 7
40 2
1
13 6
5
25 23
11 9
7 6
35 25
24 12
1
23 6
3
8 1
47 13
33 8
4
46
<4891 bytes omitted>-1
6
-1
6
3209
-1
29
-1
-1
2738
68
-1
-1
116
-1
-1
-1
-1
1162
1171
13
2
3
762
<791 bytes omitted>用户输出
-1
6
-1
6
3209
-1
29
-1
-1
2738
68
-1
-1
116
-1
-1
-1
-1
1162
1171
13
2
3
76209
-1
101
-1
-1
-1
-1
-1
-1
11
-1
-1
-1
-1
-1
1
-1
<563 bytes omitted>系统信息
Exited with return code 0200
3
41 39
35 14
16 9
1
21 20
2
17 3
45 17
5
47 5
21 6
14 10
36 2
12 10
2
26 5
46
<5218 bytes omitted>5369
20
377
-1
473
-1
-1
-1
577
38
125
-1
-1
-1
-1
-1
-1
-1
237461
-1
450
5594
<773 bytes omitted>用户输出
5369
20
377
-1
473
-1
-1
-1
577
38
125
-1
-1
-1
-1
-1
-1
-1
237461
-1
450
5594
4
-1
-1
-1
592109
31
15
-1
-1
-1
-1
2248
-1
-1
-1
<545 bytes omitted>系统信息
Exited with return code 0200
1
28 20
1
8 2
1
37 31
3
20 16
11 2
34 15
3
10 4
12 8
20 17
1
40 31
5
12 11
40
<4818 bytes omitted>20
2
31
-1
-1
31
71795
3057
25
278144
1
4
-1
881
1
-1
15
21
-1
-1
154768371
-1
<768 bytes omitted>用户输出
20
2
31
-1
-1
31
71795
3057
25
278144
1
4
-1
881
1
-1
15
21
-1
-1
154768371
-1
6066
2
-1
-1
6
7
-1
-1
1046
8
-1
-1
-1
-1
-1
4197
<540 bytes omitted>系统信息
Exited with return code 0200
2
21 20
14 10
2
30 7
16 8
2
34 10
27 12
1
13 4
5
18 12
43 5
43 17
20 9
38 6
2
<4930 bytes omitted>-1
-1
282
4
-1
241
14
-1
-1
18
495296
-1
-1
-1
529
-1
-1
-1
-1
-1
-1
34616068
<786 bytes omitted>用户输出
-1
-1
282
4
-1
241
14
-1
-1
18
495296
-1
-1
-1
529
-1
-1
-1
-1
-1
-1
34616068
1476182
7408
-1
-1
-1
1646
57632
-1
-1
718455
-1
-
<558 bytes omitted>系统信息
Exited with return code 0200
3
6 3
40 23
50 30
6
34 29
28 10
46 5
46 4
50 48
40 21
4
30 13
18 3
10 5
27 16
5
<5050 bytes omitted>-1
-1
-1
-1
-1
-1
18964
2599
-1
16
-1
345
9
-1
-1
-1
-1
-1
790
396
-1
331
6527
<781 bytes omitted>用户输出
-1
-1
-1
-1
-1
-1
18964
2599
-1
16
-1
345
9
-1
-1
-1
-1
-1
790
396
-1
331
6527
-1
-1
-1
17
4
9948
-1
-1
-1
-1
-1
1
4634
6631
-1
<553 bytes omitted>系统信息
Exited with return code 0200
6
14 10
33 19
31 20
40 34
35 21
7 4
4
31 3
44 8
11 6
46 2
3
43 34
19 6
10 6
4
<4925 bytes omitted>-1
-1
6656
-1
-1
213365705
-1
-1
922
4081096
21
1007
18
-1
-1
7913
-1
-1
12
64145
<833 bytes omitted>用户输出
-1
-1
6656
-1
-1
213365705
-1
-1
922
4081096
21
1007
18
-1
-1
7913
-1
-1
12
64145
-1
-1
-1
795
-1
152688
228
-1
-1
-1
377
-1
782
<605 bytes omitted>系统信息
Exited with return code 0200
2
49 23
7 5
3
34 27
32 23
22 9
4
29 20
24 18
28 26
11 4
6
34 32
37 23
14 6
47 3
<4896 bytes omitted>-1
5399
50538
-1
-1
1592
-1
-1
17
-1
-1
-1
-1
204
23
-1
-1
-1
34
-1
120501
-1
<778 bytes omitted>用户输出
-1
5399
50538
-1
-1
1592
-1
-1
17
-1
-1
-1
-1
204
23
-1
-1
-1
34
-1
120501
-1
-1
-1
-1
2
-1
-1
-1
4
7
249
-1
-1
116
245398803
-1
<550 bytes omitted>系统信息
Exited with return code 0200
1
7 2
4
11 4
28 5
12 11
36 34
4
28 6
27 8
13 5
29 4
6
47 30
11 2
11 7
42 17
26
<5134 bytes omitted>2
-1
219302
-1
5
-1
-1
-1
-1
-1
-1
-1
-1
6251
274620
-1
689
319607
-1
-1
-1
-1
<779 bytes omitted>用户输出
2
-1
219302
-1
5
-1
-1
-1
-1
-1
-1
-1
-1
6251
274620
-1
689
319607
-1
-1
-1
-1
-1
-1
-1
-1
24
10
7407
-1
1098
-1
-1
-1
-1
-1
111
<551 bytes omitted>系统信息
Exited with return code 0