QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#742307#9622. 有限小数supepapupu#WA 10ms3556kbC++232.0kb2024-11-13 16:19:482024-11-13 16:19:52

Judging History

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

  • [2024-11-13 16:19:52]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:3556kb
  • [2024-11-13 16:19:48]
  • 提交

answer

#include <bits/stdc++.h>

#define DEBUG
#ifdef DEBUG
#define debug(x) cerr << #x << ": " << (x) << endl
#define print(x) cerr << x << ' '
#define println(x) cerr << x << endl
#else
#define debug(x)
#define print(x)
#define println(x)
#endif
#define x first
#define y second
#define el '\n'
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int N = 3e5 + 10, INF = 0x3f3f3f3f, mod = 998244353;

int gao(int x) {
    while (x % 2 == 0) x /= 2;
    while (x % 5 == 0) x /= 5;
    return x;
}

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

void solve() {
    int a, b; cin >> a >> b;
    if (gao(b) == 1) return cout << "0 1" << el, void();
    int c = b - a, d = b;
    vector<int> nums;
    static constexpr int N = 1000000000;
    for (ll x = 1; x <= N; x *= 2) 
        for (ll y = 1; x * y <= N; y *= 5) 
            nums.emplace_back(x * y);
    for (ll k: nums) {
        if (k == 1) continue;
        if (b % k == 0) {
            auto wk = [&]() -> void {
                ll p = gao(b);
                ll x, y;
                ll g = exgcd(p, k, x, y);
                if (a % g) return;
                ll A = a, P = p, K = k;
                A /= g, P /= g, K /= g, x *= a, y *= a;
                ll t = y / P;
                y -= t * P;
                if (y > 0) y -= P;
                ll res = -y;
                if (res < c) c = res, d = b / k;
            };
        }
        if (b * k <= N) {
            ll p = gao(b);
            // if (b * k == 4375) debug(p); debug(k); debug(a);
            ll x = (a * k + p - 1) / p;
            ll res = p * x - a * k;
            if (res < c) c = res, d = b * k;
        }
    }
    cout << c << ' ' << d << el;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int tcase = 1;
    cin >> tcase;
    while (tcase--) solve();
}

详细

Test #1:

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

input:

4
1 2
2 3
3 7
19 79

output:

0 1
1 3
1 4375
3 316

result:

ok 4 case(s)

Test #2:

score: -100
Wrong Answer
time: 10ms
memory: 3556kb

input:

10000
11 12
28 53
17 60
2 35
17 181
80 123
68 141
79 163
71 99
13 64
33 61
15 32
16 61
11 86
33 74
128 143
40 53
7 23
30 31
5 6
86 181
73 91
13 23
71 81
1 2
7 38
117 160
33 83
129 151
88 153
25 58
16 19
19 141
95 124
43 96
71 139
11 59
106 109
93 152
34 43
17 99
1 57
20 159
16 25
5 73
159 170
172 17...

output:

1 12
1 828125000
1 1500
1 109375
1 231680000
23 960937500
1 36096000
5 326
1 63360
0 1
1 61000
0 1
1 4880
1 10750
1 18500
1 11714560
1 331250
1 898437500
1 31
1 6
1 289600000
1 455000
1 115000000
1 1265625
0 1
1 29687500
0 1
1 415
1 235937500
1 765000000
1 181250
1 2968750
1 4406250
3 24800
1 480
3 ...

result:

wrong answer Jury found better answer than participant's 1 < 2 (Testcase 321)