QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #751812 | #9622. 有限小数 | walili# | WA | 434ms | 3860kb | C++20 | 9.3kb | 2024-11-15 20:50:46 | 2024-11-15 20:50:46 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using lll = __int128;
using ll = long long;
#define endl '\n'
const lll inf= 1e17;
const lll mod = 998244353;
const vector<lll> denoms = {
1, 2, 4, 5, 8,
10, 16, 20, 25, 32,
40, 50, 64, 80, 100,
125, 128, 160, 200, 250,
256, 320, 400, 500, 512,
625, 640, 800, 1000, 1024,
1250, 1280, 1600, 2000, 2048,
2500, 2560, 3125, 3200, 4000,
4096, 5000, 5120, 6250, 6400,
8000, 8192, 10000, 10240, 12500,
12800, 15625, 16000, 16384, 20000,
20480, 25000, 25600, 31250, 32000,
32768, 40000, 40960, 50000, 51200,
62500, 64000, 65536, 78125, 80000,
81920, 100000, 102400, 125000, 128000,
131072, 156250, 160000, 163840, 200000,
204800, 250000, 256000, 262144, 312500,
320000, 327680, 390625, 400000, 409600,
500000, 512000, 524288, 625000, 640000,
655360, 781250, 800000, 819200, 1000000,
1024000, 1048576, 1250000, 1280000, 1310720,
1562500, 1600000, 1638400, 1953125, 2000000,
2048000, 2097152, 2500000, 2560000, 2621440,
3125000, 3200000, 3276800, 3906250, 4000000,
4096000, 4194304, 5000000, 5120000, 5242880,
6250000, 6400000, 6553600, 7812500, 8000000,
8192000, 8388608, 9765625, 10000000, 10240000,
10485760, 12500000, 12800000, 13107200, 15625000,
16000000, 16384000, 16777216, 19531250, 20000000,
20480000, 20971520, 25000000, 25600000, 26214400,
31250000, 32000000, 32768000, 33554432, 39062500,
40000000, 40960000, 41943040, 48828125, 50000000,
51200000, 52428800, 62500000, 64000000, 65536000,
67108864, 78125000, 80000000, 81920000, 83886080,
97656250, 100000000, 102400000, 104857600, 125000000,
128000000, 131072000, 134217728, 156250000, 160000000,
163840000, 167772160, 195312500, 200000000, 204800000,
209715200, 244140625, 250000000, 256000000, 262144000,
268435456, 312500000, 320000000, 327680000, 335544320,
390625000, 400000000, 409600000, 419430400, 488281250,
500000000, 512000000, 524288000, 536870912, 625000000,
640000000, 655360000, 671088640, 781250000, 800000000,
819200000, 838860800, 976562500, 1000000000, 1024000000,
1048576000, 1073741824, 1220703125, 1250000000, 1280000000,
1310720000, 1342177280, 1562500000, 1600000000, 1638400000,
1677721600, 1953125000, 2000000000, 2048000000, 2097152000,
2147483648, 2441406250, 2500000000, 2560000000, 2621440000,
2684354560, 3125000000, 3200000000, 3276800000, 3355443200,
3906250000, 4000000000, 4096000000, 4194304000, 4294967296,
4882812500, 5000000000, 5120000000, 5242880000, 5368709120,
6103515625, 6250000000, 6400000000, 6553600000, 6710886400,
7812500000, 8000000000, 8192000000, 8388608000, 8589934592,
9765625000, 10000000000, 10240000000, 10485760000, 10737418240,
12207031250, 12500000000, 12800000000, 13107200000, 13421772800,
15625000000, 16000000000, 16384000000, 16777216000, 17179869184,
19531250000, 20000000000, 20480000000, 20971520000, 21474836480,
24414062500, 25000000000, 25600000000, 26214400000, 26843545600,
30517578125, 31250000000, 32000000000, 32768000000, 33554432000,
34359738368, 39062500000, 40000000000, 40960000000, 41943040000,
42949672960, 48828125000, 50000000000, 51200000000, 52428800000,
53687091200, 61035156250, 62500000000, 64000000000, 65536000000,
67108864000, 68719476736, 78125000000, 80000000000, 81920000000,
83886080000, 85899345920, 97656250000, 100000000000, 102400000000,
104857600000, 107374182400, 122070312500, 125000000000, 128000000000,
131072000000, 134217728000, 137438953472, 152587890625, 156250000000,
160000000000, 163840000000, 167772160000, 171798691840, 195312500000,
200000000000, 204800000000, 209715200000, 214748364800, 244140625000,
250000000000, 256000000000, 262144000000, 268435456000, 274877906944,
305175781250, 312500000000, 320000000000, 327680000000, 335544320000,
343597383680, 390625000000, 400000000000, 409600000000, 419430400000,
429496729600, 488281250000, 500000000000, 512000000000, 524288000000,
536870912000, 549755813888, 610351562500, 625000000000, 640000000000,
655360000000, 671088640000, 687194767360, 762939453125, 781250000000,
800000000000, 819200000000, 838860800000, 858993459200, 976562500000,
1000000000000, 1024000000000, 1048576000000, 1073741824000, 1099511627776,
1220703125000, 1250000000000, 1280000000000, 1310720000000, 1342177280000,
1374389534720, 1525878906250, 1562500000000, 1600000000000, 1638400000000,
1677721600000, 1717986918400, 1953125000000, 2000000000000, 2048000000000,
2097152000000, 2147483648000, 2199023255552, 2441406250000, 2500000000000,
2560000000000, 2621440000000, 2684354560000, 2748779069440, 3051757812500,
3125000000000, 3200000000000, 3276800000000, 3355443200000, 3435973836800,
3814697265625, 3906250000000, 4000000000000, 4096000000000, 4194304000000,
4294967296000, 4398046511104, 4882812500000, 5000000000000, 5120000000000,
5242880000000, 5368709120000, 5497558138880, 6103515625000, 6250000000000,
6400000000000, 6553600000000, 6710886400000, 6871947673600, 7629394531250,
7812500000000, 8000000000000, 8192000000000, 8388608000000, 8589934592000,
8796093022208, 9765625000000, 10000000000000, 10240000000000, 10485760000000,
10737418240000, 10995116277760, 12207031250000, 12500000000000, 12800000000000,
13107200000000, 13421772800000, 13743895347200, 15258789062500, 15625000000000,
16000000000000, 16384000000000, 16777216000000, 17179869184000, 17592186044416,
19073486328125, 19531250000000, 20000000000000, 20480000000000, 20971520000000,
21474836480000, 21990232555520, 24414062500000, 25000000000000, 25600000000000,
26214400000000, 26843545600000, 27487790694400, 30517578125000, 31250000000000,
32000000000000, 32768000000000, 33554432000000, 34359738368000, 35184372088832,
38146972656250, 39062500000000, 40000000000000, 40960000000000, 41943040000000,
42949672960000, 43980465111040, 48828125000000, 50000000000000, 51200000000000,
52428800000000, 53687091200000, 54975581388800, 61035156250000, 62500000000000,
64000000000000, 65536000000000, 67108864000000, 68719476736000, 70368744177664,
76293945312500, 78125000000000, 80000000000000, 81920000000000, 83886080000000,
85899345920000, 87960930222080, 95367431640625, 97656250000000, 100000000000000,
102400000000000, 104857600000000, 107374182400000, 109951162777600, 122070312500000,
125000000000000, 128000000000000, 131072000000000, 134217728000000, 137438953472000,
140737488355328, 152587890625000, 156250000000000, 160000000000000, 163840000000000,
167772160000000, 171798691840000, 175921860444160, 190734863281250, 195312500000000,
200000000000000, 204800000000000, 209715200000000, 214748364800000, 219902325555200,
244140625000000, 250000000000000, 256000000000000, 262144000000000, 268435456000000,
274877906944000, 281474976710656, 305175781250000, 312500000000000, 320000000000000,
327680000000000, 335544320000000, 343597383680000, 351843720888320, 381469726562500,
390625000000000, 400000000000000, 409600000000000, 419430400000000, 429496729600000,
439804651110400, 476837158203125, 488281250000000, 500000000000000, 512000000000000,
524288000000000, 536870912000000, 549755813888000, 562949953421312, 610351562500000,
625000000000000, 640000000000000, 655360000000000, 671088640000000, 687194767360000,
703687441776640, 762939453125000, 781250000000000, 800000000000000, 819200000000000,
838860800000000, 858993459200000, 879609302220800, 953674316406250, 976562500000000,
1000000000000000
};
lll gcd(lll a, lll b) {
return b == 0 ? a : gcd(b, a % b);
}
void oper(lll testcase) {
int aa = 0, bb = 0;
lll a = 0, b = 0, e = 0, f = 0, c = 0, d = 0, divisor = 0, best_c = 0, best_d = 0;
cin >> aa >> bb;
a = aa;
b = bb;
if (find(denoms.begin(), denoms.end(), b) != denoms.end()) {
cout << "0 1\n";
return;
}
best_c = inf;
for (lll denom : denoms) {
f = denom;
e = (a * f + b - 1) / b;
for (lll i = 0; i < 10; ++i) {
c = b * e - a * f;
d = b * f;
divisor = gcd(c, d);
c /= divisor;
d /= divisor;
if (d <= 1'000'000'000 && c < best_c) {
best_c = c;
best_d = d;
}
if (c == 1) {
cout << (ll)best_c << ' ' << (ll)best_d << '\n';
return;
}
++e;
}
}
cout << (ll)best_c << ' ' << (ll)best_d << '\n';
}
int main() {
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int ttt = 1;
cin >> ttt;
for (lll i = 1; i <= ttt; i++) {
oper(i);
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3860kb
input:
4 1 2 2 3 3 7 19 79
output:
0 1 1 3 1 14 3 316
result:
ok 4 case(s)
Test #2:
score: -100
Wrong Answer
time: 434ms
memory: 3640kb
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 54272 1 60 1 7 1 231680000 23 3936 1 36096000 5 326 1 63360 0 1 1 31232 0 1 1 4880 1 10750 1 18500 1 11714560 1 331250 1 2944 1 31 1 6 1 289600000 1 455000 1 58880 1 51840 0 1 1 304 0 1 1 415 1 19328000 1 765000000 1 4640 1 608 1 72192 3 775 1 480 3 347500 1 944 1 43600 1 76 1 430000 1 6336 1...
result:
wrong answer Jury found better answer than participant's 1 < 2 (Testcase 8812)