QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#745843 | #9748. 最大公因数的平方和 | hhoppitree# | RE | 3569ms | 37776kb | C++17 | 2.2kb | 2024-11-14 11:56:41 | 2024-11-14 15:54:51 |
Judging History
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...