QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#556641 | #6440. Xingqiu's Joke | rikka_lyly | WA | 259ms | 3632kb | C++20 | 1.5kb | 2024-09-10 19:53:34 | 2024-09-10 19:53:34 |
Judging History
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'