QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#760475 | #9622. 有限小数 | 1205691775 | WA | 0ms | 3644kb | C++23 | 3.0kb | 2024-11-18 17:05:36 | 2024-11-18 17:05:36 |
Judging History
answer
#pragma optimize GCC("Ofast")
#include <bits/stdc++.h>
using i64 = long long;
constexpr int fk_max = 1e9;
__int128 gcd(__int128 a, __int128 b) {
return b == 0 ? a : gcd(b, a % b);
}
std::array<i64, 3> exgcd(i64 a, i64 b) {
if (b == 0) {
return {a, 1, 0};
}
auto [g, x, y] = exgcd(b, a % b);
return {g, y, x - a / b * y};
}
i64 inline floor(i64 a, i64 b) {
return a / b - ((a ^ b) < 0 && a % b);
}
i64 inline ceil(i64 a, i64 b) {
return -floor(-a, b);
}
std::array<i64, 2> inline valid(i64 a, i64 b, i64 c, i64 d, i64 x, i64 y) {
// auto [d, x, y] = exgcd(a, b);
if (c % d) return {0, -1};
x *= c / d;
y *= c / d;
i64 dx = b / d;
i64 dy = -a / d;
// std::cerr << a << " " << b << " " << c << " " << x << " " << y << " " << "\n";
i64 k = dx > 0 ? ceil(-x, dx) : floor(-x, dx);
x += k * dx, y += k * dy;
// std::cerr << a << " " << b << " " << c << " " << x << " " << y << " " << "\n";
return {y >= 0, x};
}
using namespace std;
map<pair<int,int>,pair<int,int>> ans;
void solve(){
i64 a, b;
std::cin >> a >> b;
if (ans.count({a, b})) {
auto [c,d] = ans[{a,b}];
cout<< c<< ' '<<d<< '\n';
return;
}
i64 remb = b;
while(remb % 2 == 0){
remb /= 2;
}
while(remb % 5 == 0) {
remb /= 5;
}
std::vector<i64> zy;
for (int i = 1; 1ll * i * i <= remb; ++i) {
if (remb % i == 0) {
zy.push_back(i);
}
if (1ll * i * i == remb) continue;
zy.push_back(remb / i);
}
std::sort(std::begin(zy), std::end(zy));
i64 c = 1e18, d = 1e18;
__int128 cx_a = a;
if (cx_a % remb == 0) {
std::cout << "0 1\n";
return;
}
// ad + bc + xbd = 0
// for (auto zz : zy) {
auto [g, x, y] = exgcd(b, -remb);
// i64 cnt = 0;
for(i64 i = 1; i <= fk_max; i = i * 2) {
for (i64 j = i; j <= fk_max; j *= 5) {
// cnt++;
// continue;
i64 dd = j ;
if (dd > fk_max) break;
auto [ok, cc] = valid(b, - remb , - a * dd, g, x, y);
if (!ok) continue;
// std::cerr << ": " << dd << "\n";
// i64 gg = std::gcd(cc, dd);
// cc /= gg;
// dd /= gg;
if (cc < c) {
c = cc;
d = dd;
if (c == 1) break;
} else if (cc == c) {
d = std::min(dd, d);
}
}
}
// std::cout<< cnt<< '\n';
// break;
// }
std::cout << c << " ";
std::cout << d;
std::cout << "\n";
ans[{a,b}] = {c,d};
}
int main() {
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
int t;
std::cin >> t;
while(t--){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3644kb
input:
4 1 2 2 3 3 7 19 79
output:
0 1 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000
result:
wrong answer Integer 1000000000000000000 violates the range [0, 10^9]