QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#745843#9748. 最大公因数的平方和hhoppitree#RE 3569ms37776kbC++172.2kb2024-11-14 11:56:412024-11-14 15:54:51

Judging History

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

  • [2024-11-14 15:54:51]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:RE
  • 用时:3569ms
  • 内存:37776kb
  • [2024-11-14 15:54:45]
  • hack成功,自动添加数据
  • (/hack/1180)
  • [2024-11-14 11:56:42]
  • 评测
  • 测评结果:100
  • 用时:3354ms
  • 内存:37672kb
  • [2024-11-14 11:56:41]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5, M = 2e6 + 5;

int a[N], b[N], p1[N], c[M], p2[N], d[M], cnt1[N], cnt2[N];
vector<int> D[N];
unsigned int f[N], res[N];

struct op {
    int l, r, id;
} p[N << 2];

int sz;

int cmp(op x, op y) {
    return ((x.l - 1) / sz + 1 != (y.l - 1) / sz + 1 ? x.l < y.l : (((x.l - 1) / sz + 1) & 1) ? x.r < y.r : x.r > y.r);
}

signed main() {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i) scanf("%d", &b[i]);
    for (int i = 1; i <= n; ++i) {
        f[i] += i * i;
        for (int j = i + i; j <= n; j += i) f[j] -= f[i];
        for (int j = i; j <= n; j += i) D[j].push_back(i);
    }
    for (int i = 1; i <= n; ++i) {
        p1[i] = p1[i - 1];
        for (auto j : D[a[i]]) {
            c[++p1[i]] = j;
        }
    }
    for (int i = 1; i <= n; ++i) {
        p2[i] = p2[i - 1];
        for (auto j : D[b[i]]) {
            d[++p2[i]] = j;
        }
    }
    int q, z = 0; scanf("%d", &q);
    for (int i = 1; i <= q; ++i) {
        int l1, r1, l2, r2; scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        l1 = p1[l1 - 1] + 1, r1 = p1[r1];
        l2 = p2[l2 - 1] + 1, r2 = p2[r2];
        p[++z] = {l1 - 1, l2 - 1, i};
        p[++z] = {l1 - 1, r2, -i};
        p[++z] = {r1, l2 - 1, -i};
        p[++z] = {r1, r2, i};
    }
    sz = z / sqrt(p1[n]);
    sort(p + 1, p + z + 1, cmp);
    int z1 = 0, z2 = 0;
    unsigned int now = 0;
    for (int i = 1; i <= z; ++i) {
        while (z1 < p[i].l) {
            ++z1;
            now += cnt2[c[z1]];
            cnt1[c[z1]] += f[c[z1]];
        }
        while (z2 < p[i].r) {
            ++z2;
            now += cnt1[d[z2]];
            cnt2[d[z2]] += f[d[z2]];
        }
        while (z1 > p[i].l) {
            now -= cnt2[c[z1]];
            cnt1[c[z1]] -= f[c[z1]];
            --z1;
        }
        while (z2 > p[i].r) {
            now -= cnt1[d[z2]];
            cnt2[d[z2]] -= f[d[z2]];
            --z2;
        }
        res[abs(p[i].id)] += (p[i].id / abs(p[i].id) * now);
    }
    for (int i = 1; i <= q; ++i) printf("%u\n", res[i]);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 14160kb

input:

5
4 1 5 3 2
1 2 3 4 5
5
3 3 2 3
3 4 2 4
3 4 3 4
5 5 1 1
1 1 2 2

output:

2
14
12
1
4

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 3ms
memory: 14260kb

input:

1000
564 82 818 337 917 532 941 590 783 74 256 176 714 159 262 803 869 716 12 448 523 981 664 533 797 520 872 966 710 103 118 101 288 113 363 356 87 475 515 641 147 374 424 788 883 496 230 157 926 942 999 220 886 509 987 99 400 458 993 343 946 684 205 4 925 727 875 939 830 95 486 870 741 846 916 321...

output:

21490984
1224951
277460
4677079
45620670
68717204
1487646
213162875
1696541
874252
822545
69652827
56058810
47821969
3261458
10540347
15664913
80605699
139540643
76151128
52126736
5245980
10101625
152049237
55449324
11352001
47057255
3509727
62148584
29861100
106478852
16350268
31181559
8679031
1564...

result:

ok 100 lines

Test #3:

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

input:

1000
840 720 960 900 936 660 756 924 360 780 864 480 540 504 420 630 600 990 672 792 576 336 810 528 912 240 816 648 880 432 560 624 828 288 588 300 700 252 612 768 800 882 684 468 980 450 180 396 972 552 702 510 168 546 888 594 896 930 312 870 1000 680 280 210 270 216 858 570 910 264 696 920 520 69...

output:

6552686
533067
169126
49
94392
15874
646003
9382
45717
1
456976
1
1
91544660
261221
4
1
73636
136002694
11087
467
697765
878
35
1
170897
96
221941
8716057
702144
623544
108101127
453642
289514
953537
14504512
11427616
146345360
16
688131
1
809601
343338
4
1
664608
1
2864172
1116528
1
304730035
47964...

result:

ok 100 lines

Test #4:

score: 0
Accepted
time: 3ms
memory: 12540kb

input:

5000
812 2241 3168 254 2304 2907 711 1116 2083 3445 755 4289 1848 2265 1481 4458 1701 4233 3301 4425 3793 1937 4891 4422 3891 556 2867 4041 1020 4089 3388 1013 729 896 870 365 1621 3506 2575 2714 4405 2449 326 3935 3480 4801 166 4269 1256 1587 4240 1503 3768 868 3997 1730 1077 2061 2353 2224 4528 27...

output:

807941321
455240624
2627537620
2424135152
2589015411
3591134314
2113263772
1298284545
3406697170
2076026315
4213807974
968114259
3793172020
1976412878
2776780447
1338391782
2380849218
3625502333
1067059142
414621999
107082133
600207777
621583381
3876041158
133853393
717061929
1404224227
527861594
68...

result:

ok 100 lines

Test #5:

score: 0
Accepted
time: 16ms
memory: 10528kb

input:

5000
4620 3360 4680 3960 4200 3780 2520 4320 3600 4800 2880 4032 3696 1680 2640 4368 2160 3120 4080 4560 3024 4752 4536 3240 4950 3168 1260 4140 2100 2940 3300 3900 3150 3276 3420 2772 1440 2400 2340 2700 4284 3840 4896 4500 4860 4788 3060 3744 3528 4410 1980 4704 2016 1800 3640 2808 4830 2184 2730 ...

output:

69632396
1247
901133646
4046059109
200952
1396802106
540629598
755337245
557588
2435483
9457953
1145548972
12
32223496
287792028
988209
4486883
6786453
2246716847
1
1957940484
112
8734547
4
980245
790140126
82212229
508
2621537
1897066516
321180652
14246
497053918
212
10
24674630
10480880
2323949
27...

result:

ok 1000 lines

Test #6:

score: 0
Accepted
time: 1468ms
memory: 23144kb

input:

50000
45360 27720 40320 42840 47520 41580 37800 32760 43680 47880 46200 36960 49140 30240 39600 25200 35280 46800 47040 37440 44352 43200 20160 33600 31680 48960 44100 34320 38640 36720 42000 23760 42120 49896 48048 48720 28560 15120 21840 33264 39312 49680 41040 31920 18480 28080 35640 22680 44880 ...

output:

815718828
443478172
3282173914
289
396943989
396611554
1975338
2396014214
977802806
649153806
3082097058
401314350
451600337
4
100
1
3771646751
30560837
333654247
3809884470
970045603
869722525
2110410996
3604590283
2527384014
20662419
1
637182038
1384384140
610655
498502364
1655899979
54241613
2162...

result:

ok 10000 lines

Test #7:

score: 0
Accepted
time: 2542ms
memory: 33688kb

input:

100000
3418 80525 16098 3672 92191 39158 48162 77249 2348 34221 50362 34993 73590 19830 69444 74955 82941 51308 20577 840 67758 35588 34786 98766 80909 6315 3648 66223 86008 68065 76929 27294 71886 57149 82889 58306 79801 30924 2317 91203 74228 57675 37774 38788 47368 44850 45842 10637 87098 799 152...

output:

3457780303
2081156670
1808934911
1202478704
2176937124
3181121167
3385683707
134249432
343433950
2826554440
367017376
3362759830
4290687402
4245631426
2555882249
4110953104
772060047
2657472896
2649991053
955818122
1087366267
24311516
2037883146
3118094190
4044302051
3663833949
3418310707
4058814864...

result:

ok 100000 lines

Test #8:

score: 0
Accepted
time: 3563ms
memory: 33524kb

input:

100000
83160 98280 95760 92400 55440 65520 85680 75600 90720 73920 87360 60480 95040 50400 81900 79200 69300 80640 93600 70560 97020 88200 84240 99792 45360 71280 51480 64680 96600 32760 86400 46200 64260 63840 91080 54600 63360 78624 36960 74880 78540 63000 75240 52920 71400 79560 88920 97440 71820...

output:

2206489642
2864339548
242264
3075727159
125698950
16169172
69185
2121109030
3138493565
623789403
2182312
4273
1
2977465308
8157
22588793
1199775775
556949531
1969
3317424756
2299154162
1
249
690224675
1291197790
19474
2366588432
290727
3459262414
4078455021
816699347
529124
1614555844
2252096477
108...

result:

ok 100000 lines

Test #9:

score: 0
Accepted
time: 3569ms
memory: 37776kb

input:

100000
83160 98280 95760 92400 55440 65520 85680 75600 90720 73920 87360 60480 95040 50400 81900 79200 69300 80640 93600 70560 97020 88200 84240 99792 45360 71280 51480 64680 96600 32760 86400 46200 64260 63840 91080 54600 63360 78624 36960 74880 78540 63000 75240 52920 71400 79560 88920 97440 71820...

output:

13047
2710082997
1169261108
16409
3948097706
513
237
3788841172
1762421938
9783920
4222451452
2726790682
984676472
662880003
461249286
3180192574
1918503864
273957
3838218112
183
2677659670
18
2381629966
1778571588
3592581162
2920300418
13725
166628
4233781373
3125900012
2186961810
358
58320
1197721...

result:

ok 100000 lines

Test #10:

score: 0
Accepted
time: 145ms
memory: 16660kb

input:

200
15 192 117 43 111 180 68 132 30 83 44 26 21 19 196 141 112 4 104 70 136 179 102 62 76 145 50 88 38 42 200 134 106 137 194 154 35 7 2 187 122 184 78 195 108 155 147 80 82 115 12 11 144 96 40 126 110 74 118 139 121 95 93 188 197 34 47 107 162 51 18 89 182 65 23 191 97 10 149 31 75 119 125 156 199 ...

output:

276734
50166
922656
5192
470570
3602
1149486
228794
738718
105910
2451278
48956
742253
1951523
250067
121378
171789
1375617
119616
35615
518316
165558
1053556
258900
824208
593496
287184
483186
538115
1176010
37384
38877
427813
242161
36780
500182
549438
41431
8008
86844
76002
103291
561194
463159
1...

result:

ok 100000 lines

Test #11:

score: 0
Accepted
time: 279ms
memory: 16856kb

input:

2000
1680 1260 1800 1440 1980 840 1848 1560 1512 1890 1320 1920 1080 1008 720 1584 1200 1620 1872 960 1344 1728 1764 900 1296 1500 756 1470 1428 360 1404 1400 1386 1380 1368 924 420 1350 1656 780 1760 1740 1820 1824 1716 1710 792 1860 1650 1638 1632 1836 1596 1540 1530 864 936 1056 1092 1944 1932 60...

output:

2191749
17307394
710681
332178855
3213237
28497912
1240356
5035949
5261815
940256
53005790
32485002
300550
7194
1826994
1830132
36027996
249714384
193842844
229549092
195915016
95199948
180
16358622
2627928
2907
536846750
18967821
13203430
15304526
8792294
33932012
113991458
12360299
6678392
1071427...

result:

ok 100000 lines

Test #12:

score: 0
Accepted
time: 192ms
memory: 22372kb

input:

20000
18480 15120 17640 19800 12600 13860 18720 15840 18900 16800 10080 16380 14280 17280 9240 7560 13440 14040 11880 19320 17160 16632 18360 15960 10920 19656 14400 19440 7920 12240 16560 13104 11088 12960 16200 9360 18000 18144 19152 13200 5040 17136 10800 13680 11760 11340 15600 8400 17820 16320 ...

output:

1204417
191744
58
71100
518
1036665672
261
34238
13695
804
26017
45750
694981266
888835633
7199
4269503946
32585
1813649060
1153718628
3111
8191058
151264996
1080
106912
456490989
2709136331
1638967144
1481803689
301
1892307674
4092460399
529341
6364
518292594
15200
4473
2121600
18816
1626514760
210...

result:

ok 100000 lines

Test #13:

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

input:

1
1
1
1
1 1 1 1

output:

1

result:

ok single line: '1'

Extra Test:

score: -3
Extra Test Failed : Runtime Error on 2

input:

5000
399 2883 4953 1303 4174 1070 2918 2249 3121 1625 2711 1142 2882 4864 2773 590 3994 3270 191 2346 3769 481 2141 169 349 3114 4536 3471 2580 3809 4108 2921 4757 1799 1402 1473 995 648 2908 1206 1259 3107 4707 3366 2017 2881 1542 587 943 2061 4538 36 89 3878 3502 3066 4489 3137 2910 2827 3580 1405...

output:


result: