QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#630673#8699. From Modular to Rationalhos_lyricAC ✓389ms4028kbC++144.8kb2024-10-11 19:52:412024-10-11 19:52:42

Judging History

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

  • [2024-10-11 19:52:42]
  • 评测
  • 测评结果:AC
  • 用时:389ms
  • 内存:4028kb
  • [2024-10-11 19:52:41]
  • 提交

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