QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#411651#8699. From Modular to RationalQingyuAC ✓370ms3744kbC++141.8kb2024-05-15 17:10:582024-05-15 17:10:59

Judging History

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

  • [2024-05-15 17:10:59]
  • 评测
  • 测评结果:AC
  • 用时:370ms
  • 内存:3744kb
  • [2024-05-15 17:10:58]
  • 提交

answer

// translated from python because 2e5 flush is too slow >:(

#include <bits/stdc++.h>
using namespace std;

const bool TEST = false;

using i128 = __int128_t;
using ll = long long;

i128 inv(i128 a, i128 m){
	a %= m;
	if (a == 1){
		return 1;
	}
	return m - (inv(m, a) * m / a);
}


const int NP = 3;
const vector<i128> primes = {2000000011, 2000000033, 2000000063};
i128 prod;
vector<i128> mults;

void init(){
	prod = 1;
	for(i128 a : primes) prod *= a;
	for(i128 a : primes){
		mults.push_back((prod / a) * inv(prod / a, a) % prod);
	}
}

mt19937 mt(64);

void solve(){
	for(i128 p : primes){
		cout << "? " << (ll)(p) << '\n';
	}
	cout << flush;
	i128 P, Q;
	vector<i128> x;
	if(TEST){
		P = mt() % (int(1e9) + 1);
		Q = (mt() % int(1e9)) + 1;
		for(i128 a : primes){
			x.push_back((P * inv(Q, a)) % a);
		}
	} else {
		for(int i = 0; i < NP; i++){
			ll r;
			cin >> r;
			x.push_back(r);
		}
	}
	i128 y = 0;
	for(int i = 0; i < NP; i++){
		y += x[i] * mults[i];
		y %= prod;
	}
	i128 ln = 0;
	i128 ld = 1;
	i128 rn = 1;
	i128 rd = 1;
	while(true){
		i128 mn = ln + rn;
		i128 md = ld + rd;
		i128 b = 0;
		if (mn * prod < md * y){
			while ((ld + (rd << b)) < int(2e9) and (ln + (rn << b)) * prod < (ld + (rd << b)) * y){
				b += 1;
			}
			ln += (rn << (b-1));
			ld += (rd << (b-1));
		} else {
			while (((ld << b) + rd) < int(2e9) and ((ln << b) + rn) * prod > ((ld << b) + rd) * y){
				b += 1;
			}
			rn += (ln << (b-1));
			rd += (ld << (b-1));
		}
		if (ld > int(1e9) or rd > int(1e9)){
			break;
		}
	}
	i128 q = min(ld, rd);
	i128 p = (q * x[0]) % primes[0];
	cout << "! " << ll(p) << " " << ll(q) << '\n';
	if (TEST) {
		assert(p * Q == P * q);
	}
}

int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	init();
	int T;
	cin >> T;
	while(T--) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3580kb

input:

3
1
1
1
1000000006
1000000017
1000000032
2
2
2

output:

? 2000000011
? 2000000033
? 2000000063
! 1 1
? 2000000011
? 2000000033
? 2000000063
! 1 2
? 2000000011
? 2000000033
? 2000000063
! 2 1

result:

ok 3 testcases passed

Test #2:

score: 0
Accepted
time: 0ms
memory: 3532kb

input:

10
1
1
1
1
1
1
500000003
1500000025
500000016
1250000008
1750000030
250000009
750000005
250000005
1750000056
1250000008
1750000030
250000009
1333333342
666666679
666666689
1000000007
1000000018
1000000033
600000004
200000004
200000007
1428571437
285714291
571428590

output:

? 2000000011
? 2000000033
? 2000000063
! 1 1
? 2000000011
? 2000000033
? 2000000063
! 1 1
? 2000000011
? 2000000033
? 2000000063
! 1 4
? 2000000011
? 2000000033
? 2000000063
! 9 8
? 2000000011
? 2000000033
? 2000000063
! 7 8
? 2000000011
? 2000000033
? 2000000063
! 9 8
? 2000000011
? 2000000033
? 20...

result:

ok 10 testcases passed

Test #3:

score: 0
Accepted
time: 2ms
memory: 3512kb

input:

100
1800000010
600000010
600000019
1000000010
1000000021
1000000036
1
1
1
1000000008
1000000019
1000000034
1666666677
333333340
333333345
500000003
1500000025
500000016
1500000010
500000010
1500000049
5
5
5
400000004
800000015
800000027
1000000006
1000000017
1000000032
500000004
1500000026
500000017...

output:

? 2000000011
? 2000000033
? 2000000063
! 1 10
? 2000000011
? 2000000033
? 2000000063
! 9 2
? 2000000011
? 2000000033
? 2000000063
! 1 1
? 2000000011
? 2000000033
? 2000000063
! 5 2
? 2000000011
? 2000000033
? 2000000063
! 7 6
? 2000000011
? 2000000033
? 2000000063
! 1 4
? 2000000011
? 2000000033
? 2...

result:

ok 100 testcases passed

Test #4:

score: 0
Accepted
time: 9ms
memory: 3508kb

input:

1000
1057142863
1971428604
542857160
666666680
1333333365
1333333385
1200000007
400000007
400000013
869565223
86956524
1304347868
1727272737
1727272756
90909094
1285714294
1857142889
714285738
1184210534
1763157925
1289473726
1666666680
333333343
333333348
978260875
847826101
717391327
657894741
186...

output:

? 2000000011
? 2000000033
? 2000000063
! 3 70
? 2000000011
? 2000000033
? 2000000063
! 29 3
? 2000000011
? 2000000033
? 2000000063
! 2 5
? 2000000011
? 2000000033
? 2000000063
! 19 23
? 2000000011
? 2000000033
? 2000000063
! 5 22
? 2000000011
? 2000000033
? 2000000063
! 17 14
? 2000000011
? 20000000...

result:

ok 1000 testcases passed

Test #5:

score: 0
Accepted
time: 41ms
memory: 3516kb

input:

10000
507288633
1562682242
104956272
1343915353
1291005314
211640220
1089041104
636986314
1226027438
413373865
6079030
1671732578
396600570
1841359805
1195467461
1251798569
1323741030
892086360
1961194041
832835835
1191044814
1977358502
1124528321
67924531
1465000009
1155000020
605000020
1760765560
...

output:

? 2000000011
? 2000000033
? 2000000063
! 162 343
? 2000000011
? 2000000033
? 2000000063
! 320 189
? 2000000011
? 2000000033
? 2000000063
! 619 292
? 2000000011
? 2000000033
? 2000000063
! 837 329
? 2000000011
? 2000000033
? 2000000063
! 440 353
? 2000000011
? 2000000033
? 2000000063
! 134 139
? 2000...

result:

ok 10000 testcases passed

Test #6:

score: 0
Accepted
time: 278ms
memory: 3524kb

input:

100000
687366171
1355460408
1385439016
669555801
658721572
78006504
1732704413
720125799
135220131
776209682
667338721
1719758119
439414118
1688415475
229027971
1205298020
754966900
1721854359
1355658207
1420323350
1558891505
1756521753
295652183
34782614
1023809530
404761912
1976190539
1806835077
1...

output:

? 2000000011
? 2000000033
? 2000000063
! 183 934
? 2000000011
? 2000000033
? 2000000063
! 924 923
? 2000000011
? 2000000033
? 2000000063
! 607 636
? 2000000011
? 2000000033
? 2000000063
! 309 992
? 2000000011
? 2000000033
? 2000000063
! 803 751
? 2000000011
? 2000000033
? 2000000063
! 19 151
? 20000...

result:

ok 100000 testcases passed

Test #7:

score: 0
Accepted
time: 283ms
memory: 3520kb

input:

100000
1990708839
1479394601
1074479280
1207738211
587958789
1697703906
1189063842
1331624580
1522763383
1772397732
244174008
56188506
1302305103
1027161962
1371898444
1757678040
1118461039
347620667
1039805402
1311366674
539141990
1536997393
1068284578
1891981979
115218049
1228119670
1144727602
788...

output:

? 2000000011
? 2000000033
? 2000000063
! 9585 6673
? 2000000011
? 2000000033
? 2000000063
! 8301 5531
? 2000000011
? 2000000033
? 2000000063
! 3925 8193
? 2000000011
? 2000000033
? 2000000063
! 6673 7724
? 2000000011
? 2000000033
? 2000000063
! 7748 6811
? 2000000011
? 2000000033
? 2000000063
! 3876...

result:

ok 100000 testcases passed

Test #8:

score: 0
Accepted
time: 316ms
memory: 3560kb

input:

100000
725399027
693980158
483599365
443791543
500898546
1503152058
696886257
1603473867
1777589550
1959778103
1393897394
525658830
1194585197
1187112975
1404831409
1204434459
88844098
646871871
1943101046
1633001489
304409722
1821857946
1889617530
1496174923
1904791908
113472947
1612134624
62441488...

output:

? 2000000011
? 2000000033
? 2000000063
! 26093 7957
? 2000000011
? 2000000033
? 2000000063
! 37382 35057
? 2000000011
? 2000000033
? 2000000063
! 1202 4721
? 2000000011
? 2000000033
? 2000000063
! 8983 1442
? 2000000011
? 2000000033
? 2000000063
! 71615 39078
? 2000000011
? 2000000033
? 2000000063
!...

result:

ok 100000 testcases passed

Test #9:

score: 0
Accepted
time: 313ms
memory: 3716kb

input:

100000
1135997843
149861368
1939676805
1517496313
401675710
969443107
1895335862
1156836695
1673775515
1824081175
1513591144
1466500813
1067059168
1382682390
1862579037
1284250025
170027471
1706036097
1650768233
724969066
1656302391
1949291241
425262195
311397959
682633249
1860644072
739467667
10294...

output:

? 2000000011
? 2000000033
? 2000000063
! 12052 14787
? 2000000011
? 2000000033
? 2000000063
! 4285 4058
? 2000000011
? 2000000033
? 2000000063
! 17177 18803
? 2000000011
? 2000000033
? 2000000063
! 11581 10448
? 2000000011
? 2000000033
? 2000000063
! 10163 13928
? 2000000011
? 2000000033
? 200000006...

result:

ok 100000 testcases passed

Test #10:

score: 0
Accepted
time: 310ms
memory: 3520kb

input:

100000
403195166
571773298
1208614775
207017456
1651189799
661476214
175058097
1674670827
562354783
1888683595
1942326859
591714413
789452362
1198759295
149874386
1658876094
426727738
520575114
355883631
297071438
74105297
887611211
23955473
742606542
370030636
119110779
168226864
1791092434
1978891...

output:

? 2000000011
? 2000000033
? 2000000063
! 65187 72109
? 2000000011
? 2000000033
? 2000000063
! 56619 38789
? 2000000011
? 2000000033
? 2000000063
! 1984 1291
? 2000000011
? 2000000033
? 2000000063
! 137547 119605
? 2000000011
? 2000000033
? 2000000063
! 147849 135727
? 2000000011
? 2000000033
? 20000...

result:

ok 100000 testcases passed

Test #11:

score: 0
Accepted
time: 315ms
memory: 3720kb

input:

100000
1536134306
1111162840
1304247952
1802675638
1313454436
1119126146
1754860298
1762370974
278381463
1582913173
70925724
1801796969
31450070
1421151569
227608078
1237166818
1259365474
1972968053
617006177
301412788
47856857
438190143
107448277
1321062633
759344282
635008998
401067145
1674422794
...

output:

? 2000000011
? 2000000033
? 2000000063
! 146750657 173614504
? 2000000011
? 2000000033
? 2000000063
! 146028280 109291851
? 2000000011
? 2000000033
? 2000000063
! 149387653 126508780
? 2000000011
? 2000000033
? 2000000063
! 162146639 127110360
? 2000000011
? 2000000033
? 2000000063
! 69914645 927479...

result:

ok 100000 testcases passed

Test #12:

score: 0
Accepted
time: 370ms
memory: 3532kb

input:

100000
1556086259
1213985416
1690145198
1406969614
1413754591
46792328
1606493387
1729942032
95882713
93361029
1623804967
887594641
1565234806
1953733839
1942599520
479740446
218480676
1399762016
1312298744
53312430
780020008
1154050331
1490841449
1487129037
1149245412
301054832
1680026586
148152442...

output:

? 2000000011
? 2000000033
? 2000000063
! 10805643 11591950
? 2000000011
? 2000000033
? 2000000063
! 181739086 106847181
? 2000000011
? 2000000033
? 2000000063
! 7186795 38369921
? 2000000011
? 2000000033
? 2000000063
! 353271183 240632957
? 2000000011
? 2000000033
? 2000000063
! 139510244 159312607
...

result:

ok 100000 testcases passed

Test #13:

score: 0
Accepted
time: 312ms
memory: 3744kb

input:

100000
1719515058
1733129463
1643785425
1132354818
769746420
1774109905
476270112
1529926317
750121931
1867670086
613652974
175161734
1438088051
1743012161
1912222569
1113202297
1386843124
291366715
1650514810
34015327
588167695
934920188
1194140801
1570355936
1427654036
580240172
1318701743
1101692...

output:

? 2000000011
? 2000000033
? 2000000063
! 954110293 683831507
? 2000000011
? 2000000033
? 2000000063
! 101827669 344093966
? 2000000011
? 2000000033
? 2000000063
! 495335459 402268500
? 2000000011
? 2000000033
? 2000000063
! 46203 76672
? 2000000011
? 2000000033
? 2000000063
! 192529826 48820623
? 20...

result:

ok 100000 testcases passed

Test #14:

score: 0
Accepted
time: 293ms
memory: 3516kb

input:

100000
190476193
604651174
1972602803
666666672
270270276
835820923
695652179
1466666692
1680000054
880000006
425531923
1506493555
1230769239
1885714318
246153855
421052635
1756097591
28169016
608695656
1066666685
640000021
1882352953
717948731
1797101507
1200000008
162162166
1701492592
1733333344
5...

output:

? 2000000011
? 2000000033
? 2000000063
! 199999998 199999999
? 2000000011
? 2000000033
? 2000000063
! 999999993 999999998
? 2000000011
? 2000000033
? 2000000063
! 999999991 999999994
? 2000000011
? 2000000033
? 2000000063
! 999999991 999999993
? 2000000011
? 2000000033
? 2000000063
! 333333332 33333...

result:

ok 100000 testcases passed

Test #15:

score: 0
Accepted
time: 316ms
memory: 3516kb

input:

100000
588235298
1005714303
1980487868
768000005
1904761937
1887005710
962162168
1536231910
582278500
654205612
1038759708
1597484328
1609756108
1255172436
1211428611
1283237002
1138461558
853333361
1969230781
735632197
649572671
1597315446
374269013
288557224
1834482770
323353300
883248760
14503816...

output:

? 2000000011
? 2000000033
? 2000000063
! 999999956 999999929
? 2000000011
? 2000000033
? 2000000063
! 999999957 999999943
? 2000000011
? 2000000033
? 2000000063
! 999999955 999999913
? 2000000011
? 2000000033
? 2000000063
! 249999989 249999988
? 2000000011
? 2000000033
? 2000000063
! 249999977 24999...

result:

ok 100000 testcases passed

Test #16:

score: 0
Accepted
time: 298ms
memory: 3528kb

input:

100000
292213476
341630908
927196683
402840545
463399117
1119300473
878950512
847557401
972816688
1238095264
976744212
958904146
629834260
137931039
763948524
1956890933
638763695
1306380333
959537580
750462122
1159369566
1410064782
1388861532
435162715
773109259
411347534
58479542
53097354
41481482...

output:

? 2000000011
? 2000000033
? 2000000063
! 499999695 499999717
? 2000000011
? 2000000033
? 2000000063
! 999999619 999999231
? 2000000011
? 2000000033
? 2000000063
! 999999747 999999167
? 2000000011
? 2000000033
? 2000000063
! 199999961 199999999
? 2000000011
? 2000000033
? 2000000063
! 333333263 33333...

result:

ok 100000 testcases passed

Test #17:

score: 0
Accepted
time: 359ms
memory: 3480kb

input:

100000
90139832
106203179
1288782572
602773588
1863928849
1754055954
1096096973
1563046652
1045157593
1697435166
1608551235
450740704
414773660
412962067
823205343
1294797703
662263339
327683634
1792237618
433923080
1753555914
284948723
1444352261
990712676
1022170369
1015133895
596476442
725557685
...

output:

? 2000000011
? 2000000033
? 2000000063
! 166665638 166665279
? 2000000011
? 2000000033
? 2000000063
! 249997844 249999091
? 2000000011
? 2000000033
? 2000000063
! 999999261 999991384
? 2000000011
? 2000000033
? 2000000063
! 999991936 999996555
? 2000000011
? 2000000033
? 2000000063
! 999994215 99999...

result:

ok 100000 testcases passed

Test #18:

score: 0
Accepted
time: 295ms
memory: 3524kb

input:

100000
1666666671
1000000008
1000000018
275862070
862745112
1728395116
181818181
60606061
1460317506
1600000008
1675675703
597014944
480000002
297872345
1974026036
64516129
679245294
891566293
1294117653
205128208
1507246424
499999996
499999996
499999996
1888888898
1000000014
1666666715
300000001
15...

output:

? 2000000011
? 2000000033
? 2000000063
! 999999991 3
? 2000000011
? 2000000033
? 2000000063
! 7 999999991
? 2000000011
? 2000000033
? 2000000063
! 1 100000000
? 2000000011
? 2000000033
? 2000000063
! 3 499999999
? 2000000011
? 2000000033
? 2000000063
! 8 999999993
? 2000000011
? 2000000033
? 2000000...

result:

ok 100000 testcases passed

Test #19:

score: 0
Accepted
time: 311ms
memory: 3740kb

input:

100000
774896269
928423251
1754149432
999999991
907692308
600000004
1146341463
1211382127
918699209
778544879
201574806
1175193835
822738390
55012225
1341075836
1485465122
636627915
1229651199
941176474
411669373
234930454
1422186759
1416470611
165517246
1291707324
1119388748
35283195
1834542824
503...

output:

? 2000000011
? 2000000033
? 2000000063
! 999999213 964
? 2000000011
? 2000000033
? 2000000063
! 999999063 65
? 2000000011
? 2000000033
? 2000000063
! 999999179 123
? 2000000011
? 2000000033
? 2000000063
! 453 999999064
? 2000000011
? 2000000033
? 2000000063
! 499999662 409
? 2000000011
? 2000000033
...

result:

ok 100000 testcases passed

Test #20:

score: 0
Accepted
time: 317ms
memory: 3536kb

input:

100000
492700771
706031845
1158594841
355062838
1412692685
461513057
15556915
191633757
607498489
997721309
1756823243
73986819
1351719433
1296681413
1533435268
893055914
382288742
622529468
18128827
1781138962
758270831
1306765035
1501952863
560827440
1600645920
392894973
1333442334
1757734984
6159...

output:

? 2000000011
? 2000000033
? 2000000063
! 999958462 94051
? 2000000011
? 2000000033
? 2000000063
! 36457 999921349
? 2000000011
? 2000000033
? 2000000063
! 999978256 53931
? 2000000011
? 2000000033
? 2000000063
! 999971645 77676
? 2000000011
? 2000000033
? 2000000063
! 70391 999910717
? 2000000011
? ...

result:

ok 100000 testcases passed

Test #21:

score: 0
Accepted
time: 281ms
memory: 3560kb

input:

100000
1427211990
1681217
1796958761
527383200
481915023
282808794
577887528
859493306
675645174
57009241
303149508
1300833568
1095160209
1180885677
1897003784
1580547500
752205271
1849078875
141834704
998889989
606073439
1750031099
331049052
140951572
1353084102
1487687756
662808992
372228262
71666...

output:

? 2000000011
? 2000000033
? 2000000063
! 4097443 994010905
? 2000000011
? 2000000033
? 2000000063
! 4093109 994536354
? 2000000011
? 2000000033
? 2000000063
! 332430737 318502
? 2000000011
? 2000000033
? 2000000063
! 8851281 996541426
? 2000000011
? 2000000033
? 2000000063
! 198158462 816047
? 20000...

result:

ok 100000 testcases passed

Test #22:

score: 0
Accepted
time: 364ms
memory: 3560kb

input:

100000
1185257419
731860274
609790987
1386360812
178287089
26202000
919751438
689263007
483995518
1110962806
1872163567
705926701
583629790
556425838
1810167841
1321002975
1949621760
1884997775
484528170
1732055833
589228999
1800194948
45392542
1898255433
1726426194
1635410151
504957917
1779200155
1...

output:

? 2000000011
? 2000000033
? 2000000063
! 879999145 742536431
? 2000000011
? 2000000033
? 2000000063
! 713509663 466284982
? 2000000011
? 2000000033
? 2000000063
! 424072063 893530853
? 2000000011
? 2000000033
? 2000000063
! 895941177 285531655
? 2000000011
? 2000000033
? 2000000063
! 31614851 722957...

result:

ok 100000 testcases passed

Test #23:

score: 0
Accepted
time: 1ms
memory: 3744kb

input:

4
1000000000
1000000000
1000000000
1818181828
606060616
1746031801
923076929
1371428595
584615404
181818184
1393939418
253968263

output:

? 2000000011
? 2000000033
? 2000000063
! 1000000000 1
? 2000000011
? 2000000033
? 2000000063
! 1 1000000000
? 2000000011
? 2000000033
? 2000000063
! 1000000000 999999999
? 2000000011
? 2000000033
? 2000000063
! 999999999 1000000000

result:

ok 4 testcases passed

Test #24:

score: 0
Accepted
time: 1ms
memory: 3536kb

input:

1
847457632
1587939725
1851528443

output:

? 2000000011
? 2000000033
? 2000000063
! 999999986 999999917

result:

ok 1 testcases passed