QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#166829 | #7074. The Answer! | ucup-team004# | WA | 105ms | 4008kb | C++20 | 4.5kb | 2023-09-06 19:03:50 | 2023-09-06 19:03:50 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 1E5;
bool isprime[N];
std::vector<int> primes;
i64 mod(i64 a, i64 p) {
if (a < 2 * p) {
return a;
}
i64 v = (a - p) / p;
a -= v * p;
return a;
}
i64 mulmod(i64 a, i64 b, i64 p) {
if (b == 0 || a <= 2 * p / b) {
return mod(a * b, p);
}
i64 res = a * b - i64(1.0L * a * b / p) * p;
res %= p;
if (res < 0) {
res += p;
}
res += p;
return res;
}
i64 power(i64 a, i64 b, i64 p) {
i64 res = 1 % p;
for (; b; b /= 2, a = mulmod(a, a, p)) {
if (b % 2) {
res = mulmod(res, a, p);
}
}
return res;
}
using Matrix = std::array<std::array<i64, 2>, 2>;
Matrix mul(const Matrix &a, const Matrix &b, i64 p) {
Matrix c{};
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
c[i][j] = mod(c[i][j] + mulmod(a[i][k], b[k][j], p), p);
}
}
}
return c;
}
i64 fib(i64 n, i64 p, i64 f0 = 0, i64 f1 = 1, i64 x = 1, i64 y = 1) {
Matrix m{x, 1, y, 0};
Matrix a{f1, f0, 0, 0};
for (; n; n /= 2, m = mul(m, m, p)) {
if (n % 2) {
a = mul(a, m, p);
}
}
return a[0][1];
}
i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {
if (!b) {
x = 1, y = 0;
return a;
}
i64 g = exgcd(b, a % b, y, x);
y -= a / b * x;
return g;
}
i64 inverse(i64 a, i64 m) {
i64 x, y;
exgcd(a, m, x, y);
x %= m;
if (x < 0) {
x += m;
}
return x;
}
int get(int x, int y, int g, int a, int p, int e) {
i64 m = 1;
for (int i = 0; i < e; i++) {
m *= p;
}
i64 phim = m / p * (p - 1);
a %= p;
i64 Fx = fib(x, phim);
i64 Fy = fib(y, phim);
i64 Fg = fib(g, phim);
i64 ax = (power(a, Fx, m) - 1) % m;
i64 ay = (power(a, Fy, m) - 1) % m;
i64 ag = (power(a, Fg, m) - 1) % m;
if (ag != 0) {
i64 m1 = 1;
while (ag % p == 0) {
ag /= p;
m1 *= p;
}
Fx = fib(x, phim * m1);
Fy = fib(y, phim * m1);
Fg = fib(g, phim * m1);
ax = (power(a, Fx, m * m1) - 1) % (m * m1) / m1;
ay = (power(a, Fy, m * m1) - 1) % (m * m1) / m1;
ag = (power(a, Fg, m * m1) - 1) % (m * m1) / m1;
i64 inv = inverse(ag, m);
return ax * ay % m * inv % m * inv % m;
}
i64 t = fib(g, m, m - 2, 1);
i64 v = g % 2 ? 1 : m - 1;
// std::cerr << "x : " << x << ", y : " << y << ", a : " << a << ", p : " << p << ", e : " << e << "\n";
// std::cerr << Fx << " " << Fy << " " << Fg << "\n";
// std::cerr << ax << " " << ay << " " << ag << "\n";
// std::cerr << "t : " << t << "\n";
return fib(x / g, m, 0, 1, t, v) * fib(y / g, m, 0, 1, t, v) % m;
}
void solve() {
int x, y, a, m;
std::cin >> x >> y >> a >> m;
std::vector<std::pair<int, int>> fac;
int tmp = m;
for (auto p : primes) {
if (p * p > m) {
break;
}
if (tmp % p == 0) {
int e = 0;
while (tmp % p == 0) {
tmp /= p;
e++;
}
fac.emplace_back(p, e);
}
}
if (tmp > 1) {
fac.emplace_back(tmp, 1);
}
int n = fac.size();
std::vector<int> v(n);
int g = std::gcd(x, y);
for (int i = 0; i < n; i++) {
auto [p, e] = fac[i];
v[i] = get(x, y, g, a, p, e);
}
int ans = 0;
for (int i = 0; i < n; i++) {
auto [p, e] = fac[i];
int pe = 1;
for (int j = 0; j < e; j++) {
pe *= p;
}
ans = (ans + 1LL * (m / pe) * inverse(m / pe, pe) % m * v[i]) % m;
}
std::cout << ans << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::fill(isprime + 2, isprime + N, true);
for (int i = 2; i < N; i++) {
if (isprime[i]) {
primes.push_back(i);
}
for (auto p : primes) {
if (i * p >= N) {
break;
}
isprime[i * p] = false;
if (i % p == 0) {
break;
}
}
}
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3796kb
input:
3 3 3 3 97 7 3 2 1901 6 12 3 100
output:
1 1761 98
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 101ms
memory: 3932kb
input:
10000 144272510 611178003 910025047 90419633 273878288 126614243 532069374 713180443 507069465 699642631 407708741 319897477 100780964 523832097 30537866 613853399 464680098 652231582 818592001 3497861 747144855 478230860 286070256 350323037 634746161 109765576 968000366 494476781 32845752 23968185 ...
output:
12358461 458245486 281357365 132976954 272470 312228465 167259963 630118388 229999939 590321282 447573918 39328575 693482753 416155988 85470325 410367926 656530932 35939208 395242216 429467226 306031639 101555997 525413089 126060782 809060867 556259277 67227456 5341844 572000084 46237958 7476350 262...
result:
ok 10000 lines
Test #3:
score: 0
Accepted
time: 104ms
memory: 3768kb
input:
10000 926756583 911666163 60821575 133776389 91130616 387682510 897210089 254849393 790241759 868616384 719217539 479273947 270135511 650627596 227968215 977893339 38369566 624063061 731582525 237849289 462428005 685553380 422651570 812994467 399496699 584305649 477758548 801102793 288021300 9676645...
output:
132953208 92334672 388622582 858596109 61553872 357010026 164428755 35007079 451309954 776150197 192224138 347153906 612802975 732989611 447066112 451179472 515939544 417490522 520532402 174530211 335655687 426943690 212829965 153596514 129191243 155923744 89893378 753666836 683444968 82570169 13191...
result:
ok 10000 lines
Test #4:
score: 0
Accepted
time: 104ms
memory: 3712kb
input:
10000 255512576 636343333 584461682 193903799 397236330 983488254 648554207 754233121 671862058 623685184 70461078 976033013 14139018 975836328 899325578 746048189 278479250 591400508 251710956 290790971 770031842 504941598 580966285 881253449 511480365 426420001 686294186 225524833 249024354 681676...
output:
153680004 194575190 259097627 422447791 172071594 195804616 145687130 488222302 83293641 26481088 86598392 140548982 511801353 743621109 489617513 258285975 673239741 311713677 536916920 115724141 234294050 25073073 159805092 758787854 33252372 364075669 77700212 474267711 83585778 22246388 54212945...
result:
ok 10000 lines
Test #5:
score: 0
Accepted
time: 101ms
memory: 3712kb
input:
10000 253454710 325664384 110873681 624184877 514191761 166400215 96844404 95554957 21278533 431205070 590015737 448544143 859479168 821587095 63286545 339319553 558710038 576255772 386910028 427851887 837245413 185397123 887946706 156137981 281019257 230210707 995969378 35577769 890046124 687934189...
output:
123948689 16733075 84724740 308500635 111279000 76580794 20631637 334231626 53490590 511061786 357944163 343563370 146623051 582535453 149957280 162495154 69015331 68387355 98516337 27474980 311193573 94813605 43018907 214366540 246323668 771851545 271406564 83638009 836771333 154994537 719006500 41...
result:
ok 10000 lines
Test #6:
score: 0
Accepted
time: 104ms
memory: 3776kb
input:
10000 668835602 274281999 796587718 562170509 853832590 741361656 903665516 848321917 31144124 902316928 500058518 383051881 696831126 55677007 967434542 235344899 121553982 399210080 503759048 378906049 408835700 583858779 109594177 922277977 267716823 14081255 785202536 330878447 438248860 3000919...
output:
333987363 23148141 42809809 120520088 377695140 552410372 71469455 580367006 54213217 248135945 753141 2562656 319538386 69770320 529358735 635060710 87355023 784514953 300446382 109546037 124567733 123041650 161599393 116954657 408521965 478952546 272898737 536262741 594650011 84678998 225414232 23...
result:
ok 10000 lines
Test #7:
score: 0
Accepted
time: 105ms
memory: 3664kb
input:
10000 851842432 616134651 882666437 116991947 520801968 818424093 281013934 51576911 485027 156313202 711796013 943566643 504931657 815754556 789124432 586176103 342937749 826931359 23603992 421300631 524889318 861050198 212815683 653987573 977719989 578000830 579115744 137707901 207215936 604965555...
output:
51958273 25108497 224967586 56060115 269090090 432542840 9332613 261964628 23310860 45287147 130502071 299517965 144137454 141062631 310999514 14391229 296954472 189161231 8742336 82463535 404709258 290066559 142375945 341882154 672823519 156631436 730578903 701326929 621830611 194538173 7781740 116...
result:
ok 10000 lines
Test #8:
score: 0
Accepted
time: 98ms
memory: 3804kb
input:
10000 347712783 161973070 424038499 68409739 77777869 881836554 575498922 137707901 392655487 625763864 62375869 810120361 230530420 40260663 92385142 686712379 449008935 75006692 258509929 132464621 591682484 455824010 63569421 908054761 132931337 239701015 677229422 937567769 66423869 619659572 62...
output:
45404888 8589607 115827444 299541167 32933054 598411606 847091330 466210881 150912918 413269422 335304993 101383137 45020293 86806799 110022476 114378384 573040784 462335371 39791326 777649253 343321265 116921300 113868892 47538456 314125820 202955898 120532278 499833134 273847784 31394333 197190208...
result:
ok 10000 lines
Test #9:
score: 0
Accepted
time: 99ms
memory: 4008kb
input:
10000 243423565 397726714 403149883 187416311 207357418 756791415 47106764 123879683 146934069 265687734 871188132 808480583 224838995 430259339 689300987 42216827 492991123 523343995 486647245 614865271 531483617 615388204 206506288 635126101 96170358 520871605 251552037 27461653 752866761 28643937...
output:
106257109 45815988 305559300 16242900 509603087 198721561 11024924 183467122 462891675 172039398 496673722 109769606 23703475 206945188 1893400 35455374 46206768 88987050 119786111 519161935 789910471 131359426 780247941 478615835 282349194 321869868 253660523 3193675 321357556 448225837 30688318 11...
result:
ok 10000 lines
Test #10:
score: 0
Accepted
time: 101ms
memory: 3932kb
input:
10000 497150364 658434844 400940636 412366219 148755563 199871618 930563701 8960453 363274254 539858146 498017204 974372627 86774070 358655545 595243377 994665871 751724830 43911492 781990459 595860127 181907113 755356314 485453764 668204249 168746218 180848162 255663659 72926759 119129003 142190876...
output:
336352946 8564710 243301058 648359224 87663261 563301058 417332 299753201 520524178 32210702 317020726 105094790 311178425 41809372 5271848 259700945 2176969 95744356 830881795 231121129 32681627 5058337 237200232 133750461 108941981 194471803 815951 614326168 61488372 150263512 205641891 56631619 1...
result:
ok 10000 lines
Test #11:
score: 0
Accepted
time: 104ms
memory: 3708kb
input:
10000 613538869 34987949 460616116 768549833 620720815 15926218 221396288 735020327 873297047 527525519 884421821 429243509 701660786 870395297 172145179 48032629 559064470 526225391 352043376 110122429 268431885 800524666 387891127 63012197 451396978 923590881 149016473 971886623 381266059 40974630...
output:
469581130 148804879 50976681 35332427 3949371 54513736 940317054 333771274 619094011 240573261 47017717 25363371 33717935 127169331 38639330 405817078 506847297 27933399 209595916 116207739 36236694 33516156 551816260 15035695 432577362 493654864 18750292 577222578 37479310 9956454 90865745 27763690...
result:
ok 10000 lines
Test #12:
score: 0
Accepted
time: 104ms
memory: 3980kb
input:
10000 485738844 929583700 601151017 740123609 485151262 545290416 918198260 945011479 203905759 198277535 863281386 817708183 510846882 676331423 659333275 282019211 101064293 479525746 325874624 211694993 97356746 578417752 869449199 59065777 639345075 425373533 486499530 992801857 698008399 169107...
output:
398920261 135668295 28796032 69199245 131249875 52470456 615495706 5612151 60989606 24907512 129672212 21092623 373721965 69191808 54258068 187730471 127318906 399393854 71011246 28310557 470623 62944356 151555372 182334418 164894734 16722173 73930082 41460901 314744782 182553842 25663187 165527339 ...
result:
ok 10000 lines
Test #13:
score: 0
Accepted
time: 105ms
memory: 3772kb
input:
10000 509566392 288831131 706055723 846672173 715552799 375579191 153215961 600306589 11661309 402389573 518222104 423681989 690854884 870104599 494255609 968991277 244431277 599352002 1888721 217260451 472505235 394766943 174333214 530991353 972781082 225755998 63262138 926203987 879201418 21435492...
output:
647223891 94530990 276686400 748623956 161236433 512070337 710026349 167755270 383248973 21721719 609302041 85508929 169293826 308136229 49742865 19682744 937559688 193489459 11839448 347010838 143941783 122490805 175054781 296372386 628199973 161233221 528727626 423095 37820312 11802102 443671836 3...
result:
ok 10000 lines
Test #14:
score: 0
Accepted
time: 100ms
memory: 3728kb
input:
10000 278108255 312198691 735890163 281242487 700090116 247560421 715411299 220143317 933329637 241766857 688322514 283771637 139815176 76049769 570594871 326363201 799607132 316385285 32284315 683260301 135610017 899426831 734712082 980796931 15496659 296177567 896010281 219373381 91215160 93553485...
output:
269976176 117727373 23531440 256534550 651738134 290482236 57931020 72193723 298722272 255117137 9837797 562024821 173494633 92285150 107267457 333300435 382671823 63901376 17837858 448389562 51782086 176821659 113119481 33091675 341816396 527814381 7812339 143898790 204388513 53663525 383977973 323...
result:
ok 10000 lines
Test #15:
score: 0
Accepted
time: 100ms
memory: 3720kb
input:
10000 114706270 661294586 754495458 843378827 265144710 291107757 789441797 393937387 312476050 788190244 78081439 713589889 325330861 501027635 734789726 625196629 422849860 834852080 976048861 175061057 282948622 239730166 935129292 491472659 384434657 867423188 279704872 565598717 863590455 67938...
output:
266183320 344375868 74843168 587662035 39498120 26358220 161954647 640800403 8780279 100389671 4139511 134090262 920615307 17823056 53429711 140706468 227989130 563437848 248684284 61465687 5441482 105061120 72746010 121831003 350986157 125248179 274410361 84322615 10238955 173264880 169665988 82471...
result:
ok 10000 lines
Test #16:
score: 0
Accepted
time: 104ms
memory: 3712kb
input:
10000 224390935 12514132 559859752 50689711 169664865 980341147 256670588 23199721 59000193 944346557 864327266 220337251 920564375 746011409 394477355 367858367 125767204 363008230 500817785 557538181 301272295 421202778 282831535 538625443 245467820 921095569 221684688 556529863 856433649 33647933...
output:
40050317 13902832 82790980 303909955 307313412 405865395 430307492 265497225 774960 478215022 799974500 82576041 78346813 53957083 103625592 360936562 4623166 152266841 83167098 479617800 725940334 335741591 636050034 446734223 6728533 256753054 63683046 136192878 404647394 246199302 204848125 31709...
result:
ok 10000 lines
Test #17:
score: -100
Wrong Answer
time: 1ms
memory: 3768kb
input:
4 15 3 1900 1901 15 3 38 19 15 75 7 11 3 3 3 2
output:
1 1 5 1
result:
wrong answer 1st lines differ - expected: '305', found: '1'