QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#806384#9868. GCDzhangwansenWA 313ms3640kbC++23553b2024-12-09 09:27:352024-12-09 09:27:36

Judging History

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

  • [2024-12-09 09:27:36]
  • 评测
  • 测评结果:WA
  • 用时:313ms
  • 内存:3640kb
  • [2024-12-09 09:27:35]
  • 提交

answer

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




int dfs(int a,int b,int dpt,int maxn)
{
    if(dpt > maxn) return 1e9;
    if(a * b == 0)
    {
        if(a+b) return 1;
        else return 0;
    }
    int GCD = __gcd(a,b);
    a /= GCD,b /= GCD;
    return  min(dfs(a - 1,b,dpt + 1,maxn),dfs(a,b - 1, dpt + 1,maxn)) + 1;
}

void solve()
{
    int a ,b;
    cin >> a >> b;
    cout << dfs(a,b,0,(log2(a) + 1) * 2) << endl;
}

signed main()
{
    int t = 1;
    cin >> t;
    while(t--)
        solve();
    return 0;
}

詳細信息

Test #1:

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

input:

3
3 4
12 20
114 514

output:

3
4
6

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3544kb

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:

ok 990 lines

Test #3:

score: -100
Wrong Answer
time: 313ms
memory: 3640kb

input:

2
4859 299556476011016293
4859 911621905353047038

output:

9
9

result:

wrong answer 1st lines differ - expected: '13', found: '9'