QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#556641#6440. Xingqiu's Jokerikka_lylyWA 259ms3632kbC++201.5kb2024-09-10 19:53:342024-09-10 19:53:34

Judging History

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

  • [2024-09-10 19:53:34]
  • 评测
  • 测评结果:WA
  • 用时:259ms
  • 内存:3632kb
  • [2024-09-10 19:53:34]
  • 提交

answer

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

#define ll long long
#define ull unsigned long long
#define int ll
#define INF 0x3f3f3f3f3f3f3f3f

void solve()
{
    int a, b;
    cin >> a >> b;
    auto getprimefact = [&](int x) -> vector<int>
    {
        vector<int> ans;
        for (int i = 2; i * i <= x; i++)
        {
            int cnt = 0;
            while (x % i == 0)
            {
                x /= i;
                cnt++;
            }
            if (cnt)
                ans.push_back(i);
        }
        if (x != 1)
            ans.push_back(x);
        return ans;
    };
    if (b < a)
        swap(a, b);
    vector<int> pfs = getprimefact(b - a);
    map<pair<int, int>, int> f;
    auto dfs = [&](auto self, int a, int c) -> int
    {
        if(a == 1)
            return 0;
        if(c == 1)
            return a - 1;
        if(f.contains({a, c}))
            return f[{a, c}];
        int ans = INF;
        for (int y : pfs)
        {
            if(c % y != 0)
                continue;
            ans = min(ans, min(self(self, a / y, c / y) + a % y, self(self, a / y + !!(a % y), c / y) + (y - a % y) % y) + 1);
        }
        // cerr << "a=" << a << " c=" << c << " ans=" << ans << endl;
        return f[{a, c}] = ans;
    };
    int ans = dfs(dfs, a, b - a);
    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3616kb

input:

5
4 7
9 8
32 84
11 35
2 1

output:

2
7
5
4
0

result:

ok 5 number(s): "2 7 5 4 0"

Test #2:

score: -100
Wrong Answer
time: 259ms
memory: 3632kb

input:

300
223528529 446621399
755625805 978718675
257717538 480810408
277875777 54782907
963091558 739998688
282469431 505562301
38752451 261845321
474429597 697522467
67026335 290119205
874629705 651536835
301964126 78871256
316864911 93772041
545942587 322849717
640801578 417708708
683070559 906163429
9...

output:

12
19
15
17
16
17
13
19
15
17
15
16
18
17
17
19
15
18
15
16
17
18
19
15
17
17
17
13
19
16
13
19
16
15
13
18
17
18
16
15
14
17
14
16
15
14
19
18
16
14
16
17
16
18
14
16
17
14
18
17
16
19
19
18
17
16
16
14
23
14
14
18
18
20
16
16
17
17
12
18
19
17
16
18
16
16
18
12
15
18
16
13
19
18
16
18
17
15
13
16
...

result:

wrong answer 12th numbers differ - expected: '15', found: '16'