QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#630668 | #8699. From Modular to Rational | hos_lyric | WA | 1ms | 3780kb | C++14 | 4.8kb | 2024-10-11 19:51:40 | 2024-10-11 19:51:41 |
Judging History
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); putchar('/'); out(u); puts(""); fflush(stdout);
#ifdef LOCAL
// P/Q = a/u
assert(P * u == a * Q);
#endif
}
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3780kb
input:
3 1 1
output:
? 999999999989 ? 999999999961 1/1 ? 999999999989
result:
wrong answer Token "1/1" doesn't correspond to pattern "?|!"