QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#411651 | #8699. From Modular to Rational | Qingyu | AC ✓ | 370ms | 3744kb | C++14 | 1.8kb | 2024-05-15 17:10:58 | 2024-05-15 17:10:59 |
Judging History
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