QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#166829#7074. The Answer!ucup-team004#WA 105ms4008kbC++204.5kb2023-09-06 19:03:502023-09-06 19:03:50

Judging History

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

  • [2023-09-06 19:03:50]
  • 评测
  • 测评结果:WA
  • 用时:105ms
  • 内存:4008kb
  • [2023-09-06 19:03:50]
  • 提交

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'