UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#186559#3344. 高精度gcd1024i100393ms1260kbC++11377b2023-10-01 09:45:432023-10-01 12:10:46

answer

#include <iostream>
using namespace std;

int solve(int a, int b) {
	if (a < b) swap(a, b);
	if (b == 0) return 0;
	if (a / b > 1) return 1;
	return solve(b, a - b) ^ 1;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int T;
	cin >> T;
	while (T--) {
		int a, b;
		cin >> a >> b;
		cout << solve(a, b) << "\n";
	}
	return 0;
}
源文件, 语言: C++11

详细

小提示：点击横条可展开更详细的信息

Test #1:

score: 5
Accepted
time: 16ms
memory: 1256kb

input:

100000
12 1
0 8
14 1
5 0
17 1
7 2
1 18
4 8
4 7
18 1
3 2
1 7
6 0
11 6
0 5
2 6
4 3
6 4
16 0
8 2
4 0
8 ...

output:

1
0
1
0
1
1
1
1
1
1
0
1
0
1
0
1
0
0
0
1
0
1
1
0
0
0
1
0
0
1
1
0
1
1
0
0
1
1
0
1
1
1
1
0
1
1
1
0
0
1
...

result:

ok 100000 lines

Test #2:

score: 5
Accepted
time: 18ms
memory: 1260kb

input:

100000
2 0
2 9
0 0
3 6
0 5
4 8
6 0
0 0
0 6
8 8
4 2
12 8
16 1
7 0
1 16
1 17
1 16
2 0
5 3
0 5
1 16
5 4...

output:

0
1
0
1
0
1
0
0
0
1
1
0
1
0
1
1
1
0
1
0
1
0
0
1
0
1
1
0
0
1
1
1
0
1
0
1
1
0
1
1
0
0
1
0
1
1
0
0
0
1
...

result:

ok 100000 lines

Test #3:

score: 5
Accepted
time: 20ms
memory: 1256kb

input:

100000
4 5
1 16
10 12
0 2
6 0
5 7
4 6
1 12
18 1
15 10
0 6
8 10
0 8
4 8
1 16
6 4
0 0
6 4
14 1
2 2
15 ...

output:

0
1
0
0
0
0
0
1
1
0
0
0
0
1
1
0
0
0
1
1
0
0
0
0
0
1
0
1
1
1
0
0
0
1
0
1
0
0
0
1
1
0
0
0
1
0
0
1
0
0
...

result:

ok 100000 lines

Test #4:

score: 5
Accepted
time: 15ms
memory: 1260kb

input:

100000
1 16
2 4
5 0
1 15
0 8
4 8
12 1
1 14
12 1
8 6
5 2
14 1
3 6
8 0
4 4
0 2
8 0
0 0
6 7
2 3
0 0
0 6...

output:

1
1
0
1
0
1
1
1
1
0
1
1
1
0
1
0
0
0
0
0
0
0
1
1
1
0
1
1
0
1
1
0
1
1
1
0
0
0
0
1
0
0
1
0
1
0
1
1
0
0
...

result:

ok 100000 lines

Test #5:

score: 5
Accepted
time: 18ms
memory: 1256kb

input:

100000
8 2
0 8
4 12
0 4
1 5
4 2
0 5
8 0
14 1
2 2
11 4
12 1
6 2
1 15
19 0
6 1
12 1
1 16
15 0
6 5
6 6
...

output:

1
0
1
0
1
1
0
0
1
1
1
1
1
1
0
1
1
1
0
0
1
0
0
0
1
1
1
0
0
1
1
1
0
0
1
1
0
0
1
0
0
1
1
0
1
0
0
1
0
1
...

result:

ok 100000 lines

Test #6:

score: 5
Accepted
time: 17ms
memory: 1260kb

input:

100000
1 0
12 1
10 10
18 0
10 15
18 1
0 9
0 12
10 4
3 0
19 10
5 4
5 2
1 2
0 9
15 10
4 0
0 5
10 15
16...

output:

0
1
1
0
0
1
0
0
1
0
1
0
1
1
0
0
0
0
0
1
1
1
0
0
0
0
1
1
0
0
0
0
1
0
0
0
1
1
1
1
0
1
0
1
0
1
0
0
1
1
...

result:

ok 100000 lines

Test #7:

score: 5
Accepted
time: 19ms
memory: 1256kb

input:

100000
3 12
1 16
1 12
4 8
6 19
12 1
1 18
0 16
7 0
5 4
12 1
7 2
7 2
5 0
12 1
0 0
1 18
4 7
16 1
16 1
7...

output:

1
1
1
1
1
1
1
0
0
0
1
1
1
0
1
0
1
1
1
1
1
1
1
1
0
1
0
1
0
0
0
1
1
0
1
1
0
1
0
1
0
0
0
0
0
1
1
1
1
0
...

result:

ok 100000 lines

Test #8:

score: 5
Accepted
time: 14ms
memory: 1260kb

input:

100000
12 5
10 10
18 4
1 14
0 4
6 10
18 1
4 8
8 6
12 1
8 8
3 8
12 1
10 6
12 1
10 2
10 0
0 11
1 0
15 ...

output:

1
1
1
1
0
1
1
1
0
1
1
1
1
1
1
1
0
0
0
1
0
1
0
0
0
0
0
1
0
1
1
1
0
1
1
0
0
1
1
0
0
0
1
0
0
0
0
0
1
1
...

result:

ok 100000 lines

Test #9:

score: 5
Accepted
time: 20ms
memory: 1260kb

input:

100000
6 2
6 65
221 554
0 10
10 6
1 16
16 1
14 1
11 0
106 718
81 215
281 984
71 504
1 12
11 7
91 369...

output:

1
1
1
0
1
1
1
1
0
1
1
1
1
1
0
1
1
1
0
1
1
1
1
1
1
1
0
1
1
1
0
1
1
0
1
1
1
1
1
1
1
1
1
0
1
0
1
0
1
0
...

result:

ok 100000 lines

Test #10:

score: 5
Accepted
time: 13ms
memory: 1260kb

input:

100000
151 812
26 128
4 12
0 8
1 13
1 14
71 790
160 1
464 51
236 716
412 11
14 3
0 0
4 0
5 7
472 146...

output:

1
1
1
0
1
1
1
1
1
1
1
1
0
0
0
1
1
1
1
1
1
1
1
0
1
0
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
0
1
1
0
1
1
1
1
...

result:

ok 100000 lines

Test #11:

score: 5
Accepted
time: 23ms
memory: 1256kb

input:

100000
261 980
4 13
463 91
978 241
16 160
0 2
517 111
111 318
1 192
91 986
56 16
5 16
594 156
855 27...

output:

1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
0
1
0
1
1
1
0
1
1
1
1
1
1
1
1
1
...

result:

ok 100000 lines

Test #12:

score: 5
Accepted
time: 20ms
memory: 1256kb

input:

100000
7 4
21 232
976 241
96 644
6 11
961 371
7 12
18 1
4 8
1 19
17 0
126 400
116 762
15 1
670 96
16...

output:

1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
0
1
1
0
1
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 100000 lines

Test #13:

score: 5
Accepted
time: 24ms
memory: 1256kb

input:

100000
6 0
18 1
5 0
6 4
126781 805800
8 10
107395891 281117263
14 1
12 11
1 16
19555421 146063439
16...

output:

0
1
0
0
1
0
1
1
0
1
1
1
1
0
0
0
1
1
1
1
0
1
1
1
1
1
1
1
0
1
0
1
1
1
0
1
1
1
0
0
1
1
1
1
0
1
1
0
1
1
...

result:

ok 100000 lines

Test #14:

score: 5
Accepted
time: 21ms
memory: 1256kb

input:

100000
7731561 121784176
1 16
13 10
473757172 72463406
2 0
38239400 15441386
17020501 164238775
3922...

output:

1
1
0
1
0
1
1
1
1
1
1
0
1
1
1
1
0
1
0
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
0
0
1
1
0
1
1
1
1
...

result:

ok 100000 lines

Test #15:

score: 5
Accepted
time: 20ms
memory: 1256kb

input:

100000
67327136 409563021
11 10
43972782 10686321
4 0
1 16
2059731 16004403
8 0
154124556 411156042
...

output:

1
0
1
0
1
1
0
1
1
1
1
0
1
1
1
1
1
0
1
1
0
1
1
1
1
1
0
1
1
1
1
1
0
1
1
1
1
0
1
1
0
1
1
1
1
1
1
1
1
1
...

result:

ok 100000 lines

Test #16:

score: 5
Accepted
time: 24ms
memory: 1256kb

input:

100000
0 14
1 16
318529120 1058971
1 14
6001526 28059309
100556690 11272836
1 15
18 1
4 14
2 0
11864...

output:

0
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
0
1
1
0
1
1
1
0
1
1
1
1
1
1
0
1
1
1
1
...

result:

ok 100000 lines

Test #17:

score: 5
Accepted
time: 24ms
memory: 1256kb

input:

100000
127635342 8334716
4 12
0 14
0 0
128124504 40221721
107277681 389999911
14 8
3012171 20742480
...

output:

1
1
0
0
1
1
1
1
1
1
0
0
1
1
1
0
1
1
0
1
1
1
1
1
0
1
0
1
1
1
1
1
1
0
1
1
1
1
1
0
0
1
1
1
1
0
1
1
1
1
...

result:

ok 100000 lines

Test #18:

score: 5
Accepted
time: 22ms
memory: 1260kb

input:

100000
17395661 60881814
39624240 5140381
57309111 223140807
16 1
8 0
36847062 2256281
217391544 589...

output:

1
1
1
1
0
1
1
0
0
0
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
...

result:

ok 100000 lines

Test #19:

score: 5
Accepted
time: 24ms
memory: 1260kb

input:

100000
11 1
4 0
15 0
16 1
12 1
1 14
121577631 411125892
46935436 12796381
541912044 221685416
198958...

output:

1
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
0
0
0
1
1
1
1
1
0
1
1
0
0
1
1
1
1
1
1
1
1
1
1
0
0
1
1
1
0
...

result:

ok 100000 lines

Test #20:

score: 5
Accepted
time: 21ms
memory: 1256kb

input:

100000
11775400 3502541
593524084 164007861
4 0
111468606 516686625
99000252 39343841
2 6
14 11
9258...

output:

1
1
0
1
1
1
0
1
1
0
1
1
1
0
1
1
0
0
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
0
1
1
1
1
1
0
1
0
1
1
1
1
1
0
1
...

result:

ok 100000 lines

中文 English

Server time: 2025-03-15 19:24:25 | 开源项目