QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#849260#9868. GCDlichenyu_acWA 3ms3536kbC++14658b2025-01-09 13:58:202025-01-09 13:58:28

Judging History

你现在查看的是最新测评结果

  • [2025-01-09 13:58:28]
  • 评测
  • 测评结果：WA
  • 用时：3ms
  • 内存：3536kb
查看
  • [2025-01-09 13:58:20]
  • 提交

answer

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int main() {
	function<ll(ll, ll)> gcd = [&](ll a, ll b) {
		return b ? gcd(b, a % b) : a;
	};

	auto solve = [&]() {
		map<pair<ll, ll>, int> d;
		ll x, y; cin >> x >> y;
		queue<pair<ll, ll>> q;
		d[{x, y}] = 0, q.emplace(x, y);
		while (q.size()) {
			auto [a, b] = q.front(); q.pop();
			if (a == 0 || b == 0) {
				cout << d[{a, b}] + 1 << endl;
				return;
			}
			ll t = gcd(a, b);
			d[{a, b - t}] = d[{a, b}] + 1, q.emplace(a, b - t);
			d[{a - t, b}] = d[{a, b}] + 1, q.emplace(a - t, b);
		}
	};

	int T; cin >> T;
	while (T--) solve();
	return 0;
}
源文件, 语言: C++14

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3488kb

input:

3
3 4
12 20
114 514

output:

3
4
6

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 3ms
memory: 3536kb

input:

990
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
2 3
2 4
2...

output:

2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3
2
3
2
3
2
3
2
3
2
3
2
3
2
3
2
3
2
3
2
3
2
3
2
3
2
3
2
3
2
3
2
3
2
3
2
3
2
3
2
3
2
3
2
3
2
3
2
3
2
3
2
3
2
3
2
3
2
3
4
2
3
3
2
3
4
2
3
3
2
3
4
2
3
3
2
3
4
2
3
3
2
3
4
2
3
3
2
3
4
2
...

result:

wrong answer 239th lines differ - expected: '4', found: '5'
English 繁體中文 简体中文

伺服器時間: 2025-01-20 22:41:56 | 開源專案