QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#630673 | #8699. From Modular to Rational | hos_lyric | AC ✓ | 389ms | 4028kb | C++14 | 4.8kb | 2024-10-11 19:52:41 | 2024-10-11 19:52:42 |
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);
}
printf("! "); out(a); printf(" "); out(u); puts(""); fflush(stdout);
#ifdef LOCAL
// P/Q = a/u
assert(P * u == a * Q);
#endif
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3744kb
input:
3 1 1 499999999995 499999999981 2 2
output:
? 999999999989 ? 999999999961 ! 1 1 ? 999999999989 ? 999999999961 ! 1 2 ? 999999999989 ? 999999999961 ! 2 1
result:
ok 3 testcases passed
Test #2:
score: 0
Accepted
time: 1ms
memory: 3748kb
input:
10 1 1 1 1 749999999992 749999999971 374999999997 874999999967 624999999994 124999999996 374999999997 874999999967 333333333331 666666666642 499999999996 499999999982 699999999993 299999999989 857142857134 857142857110
output:
? 999999999989 ? 999999999961 ! 1 1 ? 999999999989 ? 999999999961 ! 1 1 ? 999999999989 ? 999999999961 ! 1 4 ? 999999999989 ? 999999999961 ! 9 8 ? 999999999989 ? 999999999961 ! 7 8 ? 999999999989 ? 999999999961 ! 9 8 ? 999999999989 ? 999999999961 ! 4 3 ? 999999999989 ? 999999999961 ! 3 2 ? 9999999999...
result:
ok 10 testcases passed
Test #3:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
100 99999999999 899999999965 499999999999 499999999985 1 1 499999999997 499999999983 166666666666 833333333302 749999999992 749999999971 249999999999 249999999992 5 5 799999999993 199999999994 499999999995 499999999981 749999999993 749999999972 499999999996 499999999982 1 1 333333333333 666666666644...
output:
? 999999999989 ? 999999999961 ! 1 10 ? 999999999989 ? 999999999961 ! 9 2 ? 999999999989 ? 999999999961 ! 1 1 ? 999999999989 ? 999999999961 ! 5 2 ? 999999999989 ? 999999999961 ! 7 6 ? 999999999989 ? 999999999961 ! 1 4 ? 999999999989 ? 999999999961 ! 7 4 ? 999999999989 ? 999999999961 ! 5 1 ? 999999999...
result:
ok 100 testcases passed
Test #4:
score: 0
Accepted
time: 4ms
memory: 3724kb
input:
1000 614285714279 814285714254 666666666669 333333333330 399999999996 599999999977 86956521739 608695652151 772727272719 45454545453 71428571429 71428571427 355263157892 513157894718 166666666669 833333333305 597826086950 684782608669 197368421051 618421052608 416666666667 83333333335 492753623184 1...
output:
? 999999999989 ? 999999999961 ! 3 70 ? 999999999989 ? 999999999961 ! 29 3 ? 999999999989 ? 999999999961 ! 2 5 ? 999999999989 ? 999999999961 ! 19 23 ? 999999999989 ? 999999999961 ! 5 22 ? 999999999989 ? 999999999961 ! 17 14 ? 999999999989 ? 999999999961 ! 89 76 ? 999999999989 ? 999999999961 ! 25 6 ? ...
result:
ok 1000 testcases passed
Test #5:
score: 0
Accepted
time: 33ms
memory: 3808kb
input:
10000 381924198247 769679300262 169312169312 465608465592 30821917810 784246575314 103343465047 975683890542 966005665713 240793201125 122302158273 7194244605 676119402978 950746268620 728301886785 554716981111 267499999998 357499999987 291866028705 320574162667 926829268287 24390243906 788321167878...
output:
? 999999999989 ? 999999999961 ! 162 343 ? 999999999989 ? 999999999961 ! 320 189 ? 999999999989 ? 999999999961 ! 619 292 ? 999999999989 ? 999999999961 ! 837 329 ? 999999999989 ? 999999999961 ! 440 353 ? 999999999989 ? 999999999961 ! 134 139 ? 999999999989 ? 999999999961 ! 243 670 ? 999999999989 ? 999...
result:
ok 10000 testcases passed
Test #6:
score: 0
Accepted
time: 260ms
memory: 3796kb
input:
100000 964668094208 215203426116 933911159254 970747562260 209119496854 215408805024 740927419347 648185483846 848202396796 528628495320 26490066225 774834437056 874133949183 973441108508 295652173914 269565217385 630952380946 297619047608 300148588407 933135215417 698757763968 177018633534 39649681...
output:
? 999999999989 ? 999999999961 ! 183 934 ? 999999999989 ? 999999999961 ! 924 923 ? 999999999989 ? 999999999961 ! 607 636 ? 999999999989 ? 999999999961 ! 309 992 ? 999999999989 ? 999999999961 ! 803 751 ? 999999999989 ? 999999999961 ! 19 151 ? 999999999989 ? 999999999961 ! 805 866 ? 999999999989 ? 9999...
result:
ok 100000 testcases passed
Test #7:
score: 0
Accepted
time: 269ms
memory: 3728kb
input:
100000 538288625801 902592537056 489965648161 823359247845 66031978518 738435249575 928404971508 23692387364 46542357951 250036705321 140735740803 935538305736 369084475892 542459088878 656197953837 619319533644 466612951954 319568939458 636261261255 154279279274 709849435378 9723964871 436962750712...
output:
? 999999999989 ? 999999999961 ! 9585 6673 ? 999999999989 ? 999999999961 ! 8301 5531 ? 999999999989 ? 999999999961 ! 3925 8193 ? 999999999989 ? 999999999961 ! 6673 7724 ? 999999999989 ? 999999999961 ! 7748 6811 ? 999999999989 ? 999999999961 ! 3876 2963 ? 999999999989 ? 999999999961 ! 1983 4522 ? 9999...
result:
ok 100000 testcases passed
Test #8:
score: 0
Accepted
time: 284ms
memory: 3736kb
input:
100000 948347367091 801935402762 675442850209 196508543223 413895361148 266257148899 409847434121 652565880702 684758687747 973770407866 771765253112 49228622372 36984352813 633001422490 793989071042 353551912567 758673174821 631816511812 965693520561 917159398831 992367924144 71580420686 4120022845...
output:
? 999999999989 ? 999999999961 ! 26093 7957 ? 999999999989 ? 999999999961 ! 37382 35057 ? 999999999989 ? 999999999961 ! 1202 4721 ? 999999999989 ? 999999999961 ! 8983 1442 ? 999999999989 ? 999999999961 ! 71615 39078 ? 999999999989 ? 999999999961 ! 1193 12899 ? 999999999989 ? 999999999961 ! 27825 703 ...
result:
ok 100000 testcases passed
Test #9:
score: 0
Accepted
time: 271ms
memory: 3748kb
input:
100000 897207006145 476296747125 430014785605 735584031515 99984045099 459235228404 951665390496 226167687588 46596783458 72156806431 619950425398 943659141118 68448263308 819558727123 637662786671 912412123971 791152199533 144505801323 569609134821 37768994290 969968662943 441068941488 893081134885...
output:
? 999999999989 ? 999999999961 ! 12052 14787 ? 999999999989 ? 999999999961 ! 4285 4058 ? 999999999989 ? 999999999961 ! 17177 18803 ? 999999999989 ? 999999999961 ! 11581 10448 ? 999999999989 ? 999999999961 ! 10163 13928 ? 999999999989 ? 999999999961 ! 17740 14927 ? 999999999989 ? 999999999961 ! 19104 ...
result:
ok 100000 testcases passed
Test #10:
score: 0
Accepted
time: 233ms
memory: 4024kb
input:
100000 352854706067 31480120373 166799865941 436876434025 450813323002 118512780787 845842565102 112144141128 659308759489 736618358884 458785990461 598423364218 396693319201 348815085966 841889951674 71440278495 520664692891 881933154177 492764527194 266714012479 661797849981 400168907732 399278241...
output:
? 999999999989 ? 999999999961 ! 65187 72109 ? 999999999989 ? 999999999961 ! 56619 38789 ? 999999999989 ? 999999999961 ! 1984 1291 ? 999999999989 ? 999999999961 ! 137547 119605 ? 999999999989 ? 999999999961 ! 147849 135727 ? 999999999989 ? 999999999961 ! 125083 133195 ? 999999999989 ? 999999999961 ! ...
result:
ok 100000 testcases passed
Test #11:
score: 0
Accepted
time: 313ms
memory: 3812kb
input:
100000 737821737513 635264015706 148518602727 438759592408 268336339974 433858005729 998266931183 238041344537 347655950799 783881270555 360881062679 136726233554 211543937061 917073599670 980988454196 824598866263 629786195248 519631798026 304410973240 308304419483 321500047287 525177558859 5601203...
output:
? 999999999989 ? 999999999961 ! 146750657 173614504 ? 999999999989 ? 999999999961 ! 146028280 109291851 ? 999999999989 ? 999999999961 ! 149387653 126508780 ? 999999999989 ? 999999999961 ! 162146639 127110360 ? 999999999989 ? 999999999961 ! 69914645 92747968 ? 999999999989 ? 999999999961 ! 139252513 ...
result:
ok 100000 testcases passed
Test #12:
score: 0
Accepted
time: 389ms
memory: 3768kb
input:
100000 133606770215 540136646532 744083262237 361340614112 871526866048 103076417589 111084226921 354608724677 387772393929 136651614767 324868988868 706993772423 203458224055 266654977274 947944033800 15189935351 94764603584 18655541141 543090779001 20303444487 196915733306 818716717469 75882020839...
output:
? 999999999989 ? 999999999961 ! 10805643 11591950 ? 999999999989 ? 999999999961 ! 181739086 106847181 ? 999999999989 ? 999999999961 ! 7186795 38369921 ? 999999999989 ? 999999999961 ! 353271183 240632957 ? 999999999989 ? 999999999961 ! 139510244 159312607 ? 999999999989 ? 999999999961 ! 481212204 440...
result:
ok 100000 testcases passed
Test #13:
score: 0
Accepted
time: 329ms
memory: 4028kb
input:
100000 866094499788 220137803617 469369680834 131901083666 150657506118 608513420740 486866131047 719702107652 635365263566 747838858975 416375692645 178678435737 368791634257 311338486376 557159232792 629021716719 70868246527 30878806341 885540875913 533920559980 719970403738 703525690734 535707650...
output:
? 999999999989 ? 999999999961 ! 954110293 683831507 ? 999999999989 ? 999999999961 ! 101827669 344093966 ? 999999999989 ? 999999999961 ! 495335459 402268500 ? 999999999989 ? 999999999961 ! 46203 76672 ? 999999999989 ? 999999999961 ! 192529826 48820623 ? 999999999989 ? 999999999961 ! 66764229 47141866...
result:
ok 100000 testcases passed
Test #14:
score: 0
Accepted
time: 308ms
memory: 3736kb
input:
100000 720785728597 354565611760 486676721969 59153493117 625480046747 419728233503 304764630131 752765407241 87967644088 715920915689 466031586860 818227720242 749039906487 160543532958 337571094010 775751435298 92006033184 435492095855 697335344388 811830698593 1 1 533968413131 181772279721 920060...
output:
? 999999999989 ? 999999999961 ! 199999998 199999999 ? 999999999989 ? 999999999961 ! 999999993 999999998 ? 999999999989 ? 999999999961 ! 999999991 999999994 ? 999999999989 ? 999999999961 ! 999999991 999999993 ? 999999999989 ? 999999999961 ! 333333332 333333333 ? 999999999989 ? 999999999961 ! 99999999...
result:
ok 100000 testcases passed
Test #15:
score: 0
Accepted
time: 311ms
memory: 3996kb
input:
100000 441575455348 565507814130 965186264006 716262003800 598454977060 14247766240 708704078011 489543587480 201736055296 592233877143 523663707412 288175788332 102115676757 821149067140 977605125445 992067980415 853781964195 89469989992 711563786687 9656276580 514575371880 202756921255 59437545392...
output:
? 999999999989 ? 999999999961 ! 999999956 999999929 ? 999999999989 ? 999999999961 ! 999999957 999999943 ? 999999999989 ? 999999999961 ! 999999955 999999913 ? 999999999989 ? 999999999961 ! 249999989 249999988 ? 999999999989 ? 999999999961 ! 249999977 249999986 ? 999999999989 ? 999999999961 ! 99999994...
result:
ok 100000 testcases passed
Test #16:
score: 0
Accepted
time: 268ms
memory: 3740kb
input:
100000 703400596118 722979145179 236917563188 712354722774 195638837966 889491824913 389857686946 473493247350 719869630182 817327950442 452168386644 321950731671 671320411509 818499690868 952296067382 125261408007 209968697337 973239932518 904371531114 967759659319 785530862965 270842201332 4178469...
output:
? 999999999989 ? 999999999961 ! 499999695 499999717 ? 999999999989 ? 999999999961 ! 999999619 999999231 ? 999999999989 ? 999999999961 ! 999999747 999999167 ? 999999999989 ? 999999999961 ! 199999961 199999999 ? 999999999989 ? 999999999961 ! 333333263 333333305 ? 999999999989 ? 999999999961 ! 33333301...
result:
ok 100000 testcases passed
Test #17:
score: 0
Accepted
time: 316ms
memory: 3796kb
input:
100000 908652293430 459862110795 480435446859 631185262966 493696196682 217264794946 470158830693 409900141091 154468794747 197416731904 549123360464 960917315230 787320743894 203283016656 274938036313 254947270236 948915768486 514473463122 848412390223 141196453062 380494418675 387484055740 1148959...
output:
? 999999999989 ? 999999999961 ! 166665638 166665279 ? 999999999989 ? 999999999961 ! 249997844 249999091 ? 999999999989 ? 999999999961 ! 999999261 999991384 ? 999999999989 ? 999999999961 ! 999991936 999996555 ? 999999999989 ? 999999999961 ! 999994215 999996946 ? 999999999989 ? 999999999961 ! 99999099...
result:
ok 100000 testcases passed
Test #18:
score: 0
Accepted
time: 311ms
memory: 3800kb
input:
100000 333666666660 666999999971 888419178986 728601718529 909090909990 589743589977 815987933623 129015808253 780941479458 988938370884 455000500545 825921092227 656072264961 560621411660 499999996 499999996 444555555550 222333333324 900099999990 100099999996 824064711815 568158168546 250249999995 ...
output:
? 999999999989 ? 999999999961 ! 999999991 3 ? 999999999989 ? 999999999961 ! 7 999999991 ? 999999999989 ? 999999999961 ! 1 100000000 ? 999999999989 ? 999999999961 ! 3 499999999 ? 999999999989 ? 999999999961 ! 8 999999993 ? 999999999989 ? 999999999961 ! 1 166666665 ? 999999999989 ? 999999999961 ! 10 9...
result:
ok 100000 testcases passed
Test #19:
score: 0
Accepted
time: 274ms
memory: 3732kb
input:
100000 903528008288 409752074672 276938461521 30784615369 577243902426 252040650390 691650222377 995974191193 924206601456 75795843517 956398255801 107561046505 239902873049 881230712285 780582264733 155260958411 72914796967 693771315715 988875745218 317148580501 485683920699 811675110100 2706514719...
output:
? 999999999989 ? 999999999961 ! 999999213 964 ? 999999999989 ? 999999999961 ! 999999063 65 ? 999999999989 ? 999999999961 ! 999999179 123 ? 999999999989 ? 999999999961 ! 453 999999064 ? 999999999989 ? 999999999961 ! 499999662 409 ? 999999999989 ? 999999999961 ! 999999163 344 ? 999999999989 ? 99999999...
result:
ok 100000 testcases passed
Test #20:
score: 0
Accepted
time: 285ms
memory: 3768kb
input:
100000 67282655154 835663639907 206622068030 561092063430 285216313434 833379707371 772272014513 56169228588 270310641142 10046833011 211233278920 113532242516 681075826024 962385178791 949997637287 720044409052 35211372758 128005661531 601621242428 640361036761 14477584125 425053912098 898347481194...
output:
? 999999999989 ? 999999999961 ! 999958462 94051 ? 999999999989 ? 999999999961 ! 36457 999921349 ? 999999999989 ? 999999999961 ! 999978256 53931 ? 999999999989 ? 999999999961 ! 999971645 77676 ? 999999999989 ? 999999999961 ! 70391 999910717 ? 999999999989 ? 999999999961 ! 999921231 50849 ? 9999999999...
result:
ok 100000 testcases passed
Test #21:
score: 0
Accepted
time: 304ms
memory: 3804kb
input:
100000 252056498311 268982946409 976402207002 852796072819 728199509987 906396193183 183249075486 412395011649 864222281548 72885508060 14159164353 132266150437 972382706739 214500391710 893762665209 160949302668 867211547529 930553155361 449832043727 773149187302 519977664888 31669265821 5204697134...
output:
? 999999999989 ? 999999999961 ! 4097443 994010905 ? 999999999989 ? 999999999961 ! 4093109 994536354 ? 999999999989 ? 999999999961 ! 332430737 318502 ? 999999999989 ? 999999999961 ! 8851281 996541426 ? 999999999989 ? 999999999961 ! 198158462 816047 ? 999999999989 ? 999999999961 ! 991183320 1974481 ? ...
result:
ok 100000 testcases passed
Test #22:
score: 0
Accepted
time: 349ms
memory: 3956kb
input:
100000 954668111083 308104178382 391576379354 209546609410 327337454566 102018494035 968915450015 71632103278 925929861343 617332517413 82864982331 81083059542 616231661373 802784147816 711088030413 455329026243 803342283552 324341878757 491217744884 601645801953 602211278623 411694863268 6800507465...
output:
? 999999999989 ? 999999999961 ! 879999145 742536431 ? 999999999989 ? 999999999961 ! 713509663 466284982 ? 999999999989 ? 999999999961 ! 424072063 893530853 ? 999999999989 ? 999999999961 ! 895941177 285531655 ? 999999999989 ? 999999999961 ! 31614851 722957888 ? 999999999989 ? 999999999961 ! 397968925...
result:
ok 100000 testcases passed
Test #23:
score: 0
Accepted
time: 1ms
memory: 3732kb
input:
4 1000000000 1000000000 90909090999 358974358986 970677451961 94693028092 909090908991 641025640976
output:
? 999999999989 ? 999999999961 ! 1000000000 1 ? 999999999989 ? 999999999961 ! 1 1000000000 ? 999999999989 ? 999999999961 ! 1000000000 999999999 ? 999999999989 ? 999999999961 ! 999999999 1000000000
result:
ok 4 testcases passed
Test #24:
score: 0
Accepted
time: 1ms
memory: 3772kb
input:
1 867621010004 294981979473
output:
? 999999999989 ? 999999999961 ! 999999986 999999917
result:
ok 1 testcases passed