QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#737381#9622. 有限小数isaunoyaWA 75ms3608kbC++234.9kb2024-11-12 15:40:462024-11-12 15:40:48

Judging History

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

  • [2024-11-12 15:40:48]
  • 评测
  • 测评结果:WA
  • 用时:75ms
  • 内存:3608kb
  • [2024-11-12 15:40:46]
  • 提交

answer


#if defined(local)
#include "./noya/debug.hpp"
#else
#define debug(...) 42
#endif

#include "bits/stdc++.h"

using namespace std;
#define rep1(a) for (int i = 0; i < a; i++)
#define rep2(i, a) for (int i = 0; i < a; i++)
#define rep3(i, a, b) for (int i = a; i < b; i++)
#define rep4(i, a, b, c) for (int i = a; i < b; i += c)
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define pb emplace_back
template <typename T, typename T2> void cmin(T &x, const T2 &y) {
  x = x < y ? x : y;
}
template <typename T, typename T2> void cmax(T &x, const T2 &y) {
  x = x > y ? x : y;
}


#include <cstdint>
using ll = int64_t;
using ull = uint64_t;
namespace noya {
template <class T> constexpr T infty = 0;
template <> constexpr int infty<int> = 1010000000;
template <> constexpr ll infty<ll> = 2020000000000000000;
template <> constexpr unsigned infty<unsigned> = infty<int>;
template <>
constexpr ull infty<ull> = infty<ll>;
template <>
constexpr __int128 infty<__int128> =
    __int128(infty<ll>) * 2000000000000000000;
template <> constexpr double infty<double> = infty<ll>;
template <> constexpr long double infty<long double> = infty<ll>;
} // namespace noya


using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <class T> using vc = vector<T>;
const int INF = 1010000000;
const ll LNF = 1010000000000000000;
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define fi first
#define se second

namespace noya {}



#include <algorithm>
#include <cassert>
#include <functional>
#include <vector>

// https://github.com/the-tourist/algo/blob/master/numeric/extgcd.cpp
template <typename T> T extgcd(T a, T b, T &x, T &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  T p = b / a;
  T g = extgcd(b - p * a, a, y, x);
  x -= p * y;
  return g;
}

template <typename T> bool diophantine(T a, T b, T c, T &x, T &y, T &g) {
  if (a == 0 && b == 0) {
    if (c == 0) {
      x = y = g = 0;
      return true;
    }
    return false;
  }
  if (a == 0) {
    if (c % b == 0) {
      x = 0;
      y = c / b;
      g = abs(b);
      return true;
    }
    return false;
  }
  if (b == 0) {
    if (c % a == 0) {
      x = c / a;
      y = 0;
      g = abs(a);
      return true;
    }
    return false;
  }
  g = extgcd(a, b, x, y);
  if (c % g != 0) {
    return false;
  }
  T dx = c / a;
  c -= dx * a;
  T dy = c / b;
  c -= dy * b;
  x = dx + (T)((__int128)x * (c / g) % b);
  y = dy + (T)((__int128)y * (c / g) % a);
  g = abs(g);
  return true;
  // |x|, |y| <= max(|a|, |b|, |c|) [tested]
}

bool crt(long long k1, long long m1, long long k2, long long m2, long long &k,
         long long &m) {
  k1 %= m1;
  if (k1 < 0)
    k1 += m1;
  k2 %= m2;
  if (k2 < 0)
    k2 += m2;
  long long x, y, g;
  if (!diophantine(m1, -m2, k2 - k1, x, y, g)) {
    return false;
  }
  long long dx = m2 / g;
  long long delta = x / dx - (x % dx < 0);
  k = m1 * (x - dx * delta) + k1;
  m = m1 / g * m2;
  assert(0 <= k && k < m);
  return true;
}

// for distinct prime modulos
template <typename T>
void crt_garner(const std::vector<int> &p, const std::vector<int> &a, T &res) {
  assert(p.size() == a.size());
  auto inverse = [&](int q, int m) {
    q %= m;
    if (q < 0)
      q += m;
    int b = m, u = 0, v = 1;
    while (q) {
      int t = b / q;
      b -= t * q;
      std::swap(q, b);
      u -= t * v;
      std::swap(u, v);
    }
    assert(b == 1);
    if (u < 0)
      u += m;
    return u;
  };
  std::vector<int> x(p.size());
  for (int i = 0; i < (int)p.size(); i++) {
    assert(0 <= a[i] && a[i] < p[i]);
    x[i] = a[i];
    for (int j = 0; j < i; j++) {
      x[i] = (int)((long long)(x[i] - x[j]) * inverse(p[j], p[i]) % p[i]);
      if (x[i] < 0)
        x[i] += p[i];
    }
  }
  res = 0;
  for (int i = (int)p.size() - 1; i >= 0; i--) {
    res = res * p[i] + x[i];
  }
}

const ll L = 1e9;

void solve() {
  ll a, b;
  cin >> a >> b;

  ll w = b;
  while (w % 2 == 0)
    w /= 2;
  while (w % 5 == 0)
    w /= 5;

  array<ll, 2> ans = {b - a, b};

  if (w == 1) {
    ans = {0, 1};
  } else {

    auto solve = [&](ll m) {
      ll d = m * w;
      ll x, y;
      ll g = extgcd(b * w, -b, x, y);
      if (g < 0) {
        x = -x;
        y = -y;
        g = -g;
      }
      if (a * d % g)
        return;
      ll z = a * d / g;
      y = y * z;
      y = (y % b + b) % b;
      ll c = y;

      ll gg = gcd(c, d);
      cmin(ans, array<ll, 2>{c / gg, d / gg});
    };

    for (ll m2 = 1; b * m2 <= INF; m2 *= 2) {
      for (ll m5 = 1; b * m2 * m5 <= INF; m5 *= 5) {
        ll m = m2 * m5;
        solve(m);
      }
    }
  }
  cout << ans[0] << " " << ans[1] << "\n";
}

int main() {
  int T;
  cin >> T;
  while (T--)
    solve();
}

詳細信息

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: 75ms
memory: 3608kb

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 48
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 228)