QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#630670#8699. From Modular to Rationalhos_lyricWA 1ms3804kbC++144.8kb2024-10-11 19:52:092024-10-11 19:52:13

Judging History

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

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

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

// using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


#ifndef LIBRA_OTHER_INT128_H_
#define LIBRA_OTHER_INT128_H_

#include <stdio.h>
#include <iostream>

constexpr unsigned __int128 toUInt128(const char *s) {
  unsigned __int128 x = 0;
  for (; *s; ++s) x = x * 10 + (*s - '0');
  return x;
}
constexpr __int128 toInt128(const char *s) {
  if (*s == '-') return -toInt128(s + 1);
  __int128 x = 0;
  for (; *s; ++s) x = x * 10 + (*s - '0');
  return x;
}
unsigned __int128 inUInt128() {
  static char buf[41];
  scanf("%s", buf);
  return toUInt128(buf);
}
__int128 inInt128() {
  static char buf[41];
  scanf("%s", buf);
  return toInt128(buf);
}

void out(unsigned __int128 x) {
  static char buf[41];
  int len = 0;
  do { buf[len++] = '0' + static_cast<int>(x % 10); } while (x /= 10);
  for (int i = len; --i >= 0; ) putchar(buf[i]);
}
void out(__int128 x) {
  if (x < 0) {
    putchar('-');
    out(-static_cast<unsigned __int128>(x));
  } else {
    out(static_cast<unsigned __int128>(x));
  }
}
std::ostream &operator<<(std::ostream &os, unsigned __int128 x) {
  static char buf[41];
  int len = 0;
  do { buf[len++] = '0' + static_cast<int>(x % 10); } while (x /= 10);
  for (int i = len; --i >= 0; ) os << buf[i];
  return os;
}
std::ostream &operator<<(std::ostream &os, __int128 x) {
  if (x < 0) {
    os << '-' << -static_cast<unsigned __int128>(x);
  } else {
    os << static_cast<unsigned __int128>(x);
  }
  return os;
}

#endif  // LIBRA_OTHER_INT128_H_


// a x + b y = (+/-) gcd(a, b)
//   (a, 0): g = a, x = 1, y = 0
//   (0, b), (b, b), (-b, b) (b != 0): g = b, x = 0, y = 1
//   otherwise: 2 |x| <= |b|, 2 |y| <= |a|
// S: signed integer
template <class S> S gojo(S a, S b, S &x, S &y) {
  if (b != 0) {
    const S g = gojo(b, a % b, y, x);
    y -= (a / b) * x;
    return g;
  } else {
    x = 1;
    y = 0;
    return a;
  }
}

// x == b0  (mod m0),  x == b1  (mod m1)
// S: signed integer
template <class S>
pair<S, S> modSystem(S m0, S b0, S m1, S b1) {
  assert(m0 >= 1);
  assert(m1 >= 1);
  if ((b0 %= m0) < 0) b0 += m0;
  if ((b1 %= m1) < 0) b1 += m1;
  if (m0 < m1) {
    swap(m0, m1);
    swap(b0, b1);
  }
  // to avoid overflow
  if (m0 % m1 == 0) {
    if (b0 % m1 != b1) return make_pair(0, 0);
    return make_pair(m0, b0);
  }
  S z0, z1;
  const S g = gojo(m0, m1, z0, z1);
  b1 -= b0;
  if (b1 % g != 0) return make_pair(0, 0);
  (b1 /= g) %= m1;
  m1 /= g;
  b0 += m0 * ((z0 * b1) % m1);
  m0 *= m1;
  if (b0 < 0) b0 += m0;
  return make_pair(m0, b0);
}


using INT = __int128;

#ifdef LOCAL
INT P, Q;
#endif

INT ask(INT m) {
  printf("? "); out(m); puts(""); fflush(stdout);
#ifdef LOCAL
  INT s, t;
  gojo(Q, m, s, t);
  return (P * s) % m;
#else
  const INT y = inInt128();
  return y;
#endif
}

constexpr INT L = 1'000'000'000LL;
constexpr INT M0 = 999'999'999'989LL;
constexpr INT M1 = 999'999'999'961LL;

int main() {
  int numCases;
  scanf("%d", &numCases);
  for (int caseId = 1; caseId <= numCases; ++caseId) {
#ifdef LOCAL
    mt19937_64 rng(caseId);
    P = 1 + rng() % L;
    Q = 1 + rng() % L;
#endif
    
    const INT Y0 = ask(M0);
    const INT Y1 = ask(M1);
    const auto res = modSystem(M0, Y0, M1, Y1);
    
    // a == Y u  (M)
    // b == Y v  (M)
    INT a = res.first, b = res.second;
    INT u = 0, v = 1;
    for (; a > L; ) {
      const INT k = a / b;
      swap(a -= k * b, b);
      swap(u -= k * v, v);
    }
    out(a); printf(" "); out(u); puts(""); fflush(stdout);
    
#ifdef LOCAL
    // P/Q = a/u
    assert(P * u == a * Q);
#endif
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3804kb

input:

3
1
1

output:

? 999999999989
? 999999999961
1 1
? 999999999989

result:

wrong answer Token "1" doesn't correspond to pattern "?|!"