QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#693771 | #6440. Xingqiu's Joke | 53Dawns | TL | 0ms | 3480kb | C++23 | 1.9kb | 2024-10-31 16:43:24 | 2024-10-31 16:43:25 |
Judging History
answer
#include <bits/stdc++.h>
#pragma GCC optimize (3)
#define de(a) cout << #a << " = " << a << "\n";
#define deg(a) cout << #a << " = " << a << " ";
#define lowbit(x) ((x) & (-x))
// #define int long long
#define siz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
#define PII pair<int, int>
using ll = long long;
using ull = unsigned long long;
using namespace std;
constexpr ll inf = 1e18;
constexpr int N = 1e6 + 10;
void solve(int Case) {
int a, b;
std::cin >> a >> b;
if (a < b) std::swap(a, b);
int d = a - b, ans = b - 1;
if (d == 1) {
std::cout << ans << '\n';
return;
}
std::vector<int> h;
for (int i = 2; i * i <= d; i++) {
if (d % i == 0) {
h.push_back(i);
while (d % i == 0) d /= i;
}
}
if (d != 1) h.push_back(d);
// std::cout << "\n-----------0----------\n";
// for (auto it : h) {
// std::cout << it << ' ';
// }
// std::cout << "\n-----------1----------\n";
auto dfs = [&](auto &dfs, int na, int nb, int ct) -> void {
if (na == 0 || nb == 0) {
return;
}
if (na == 1 || nb == 1) {
ans = std::min(ans, ct);
return;
}
for (auto p : h) {
if (abs(na - nb) % p) continue;
int la = na - na % p, lb = nb - nb % p, ld = abs(la - na);
int ra = la + p, rb = lb + p, rd = abs(ra - na);
if (ld < rd) {
dfs(dfs, la / p, lb / p, ct + ld + 1);
}
else {
dfs(dfs, ra / p, rb / p, ct + ld + 1);
}
}
};
dfs(dfs, a, b, 0);
std::cout << ans << '\n';
}
signed main() {
cin.tie(0)->ios::sync_with_stdio(false);
int T = 1;
cin >> T; cin.get();
int Case = 0;
while (++Case <= T) {
solve(Case);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3480kb
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
Time Limit Exceeded
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...