QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #749062 | #9622. 有限小数 | snow_miku | WA | 128ms | 3612kb | C++20 | 2.7kb | 2024-11-14 22:31:08 | 2024-11-14 22:31:08 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
const ll INF = 1e9 + 7;
const int N = 35;
ll gcd(ll a, ll b) {
if (!b) return a;
return gcd(b, a % b);
}
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) {
x = 1;
y = 0;
return a;
}
ll d = exgcd(b, a % b, x, y);
ll t = x;
x = y;
y = t - (a / b) * y;
return d;
}
struct info {
ll p2 = 1, p5 = 1, p = 1;
};
ll pow2[N], pow5[N];
vector<pair<ll, ll>> p25;
void init() {
pow2[0] = 1;
pow5[0] = 1;
for (int i = 1;i <= 30;i++) {
pow2[i] = pow2[i - 1] * 2LL;
}
for (int i = 1;i <= 15;i++) {
pow5[i] = pow5[i - 1] * 5LL;
}
for (int i = 0;i <= 30;i++) {
if (pow2[i] <= INF) {
for (int j = 0;j <= 15;j++) {
if (pow5[j] * pow2[i] <= INF) p25.push_back(make_pair(pow2[i], pow5[j]));
else break;
}
}
else break;
}
}
info check(ll x) {
info res;
while (x % 2 == 0) {
res.p2 *= 2LL;
x /= 2;
}
while (x % 5 == 0) {
res.p5 *= 5LL;
x /= 5;
}
res.p = x;
return res;
}
void solve()
{
ll a, b; cin >> a >> b;
a %= b;
info T = check(b);
ll P = T.p;
// ll x = T.p2 * T.p5;
// cout << P << " " << T.p2 << " " << T.p5 << '\n';
if (P == 1) {
cout << 0 << " " << 1 << '\n';
return;
}
// vector<ll> fct;
// for (int i = 3;i * i <= P;i++) {
// if (P % i == 0) {
// fct.push_back(i);
// if (P % i != i) fct.push_back(P / i);
// }
// }
// for (int q : fct) {
// }
ll c = INF;
ll d = 1;
for (auto [t2, t5] : p25) {
// if (t2 < T.p2 || t5 < T.p5) continue;
ll x = 0, k = 0;
exgcd(P, -T.p2 * T.p5, k, x);
// cout << x << " " << k << << '\n';
if (k * P - x * T.p2 * T.p5 < 0) x *= -1, k *= -1;
if (k == 0) x *= t2 * t5 * a - P;
else x *= abs(t2 * t5 * a);
ll y = t2 * t5 * T.p2 * T.p5 * P;
x = (x + y) % y;
ll g = gcd(x, y);
x /= g, y /= g;
// cout << x << " " << k << '\n';
if (c > x) {
c = x, d = y;
// cout << t2 << " " << t5 << " " << P << '\n';
}
}
cout << c << " " << d << '\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
init();
// for (auto [x, y] : p25) {
// cout << x << " " << y << '\n';
// }
int t; cin >> t;
while(t--) solve();
return 0;
};
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3600kb
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: 128ms
memory: 3612kb
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 25 53 17 60 29 35 11 1810 43 123 5 282 5 326 28 99 0 1 28 61 0 1 29 122 59 86 1 37 15 143 13 53 9 46 1 31 5 6 9 362 18 91 10 23 10 81 0 1 25 38 0 1 17 166 22 151 65 153 1 29 3 19 46 705 4 -31 43 96 68 139 4 295 3 109 43 152 9 43 14 495 7 2850 59 795 0 1 23 730 23 34 7 179 10 13 19 34 7 172 11 -...
result:
wrong answer Jury found better answer than participant's 1 < 25 (Testcase 2)