QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#187055 | #3853. Lines in a grid | ucup-team004# | AC ✓ | 136ms | 134376kb | C++20 | 1.6kb | 2023-09-24 14:09:52 | 2023-09-24 14:09:53 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 1E7;
constexpr int P = 1000003;
bool isprime[N + 1];
int phi[N + 1], nphi[N + 1], n2phi[N + 1];
std::vector<int> primes;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::fill(isprime + 2, isprime + N + 1, true);
phi[1] = 1;
for (int i = 2; i <= N; i++) {
if (isprime[i]) {
primes.push_back(i);
phi[i] = i - 1;
}
for (auto p : primes) {
if (i * p > N) {
break;
}
isprime[i * p] = false;
if (i % p == 0) {
phi[i * p] = phi[i] * p;
break;
}
phi[i * p] = phi[i] * (p - 1);
}
}
for (int i = 1; i <= N; i++) {
nphi[i] = 1LL * i * phi[i] % P;
n2phi[i] = 1LL * i * nphi[i] % P;
}
for (int i = 1; i <= N; i++) {
phi[i] = (phi[i - 1] + phi[i]) % P;
nphi[i] = (nphi[i - 1] + nphi[i]) % P;
n2phi[i] = (n2phi[i - 1] + n2phi[i]) % P;
}
int Q;
std::cin >> Q;
while (Q--) {
int n;
std::cin >> n;
int ans = (1LL * (2 * n) * n % P * phi[n - 1] - (3LL * n) * nphi[n - 1] + n2phi[n - 1]) % P * 2 % P;
int m = (n - 1) / 2;
ans = (ans - 1LL * 4 * (1LL * n * (n) % P * phi[m] - 1LL * (3 * n) * nphi[m] + 1LL * 2 * n2phi[m])) % P;
if (ans < 0) {
ans += P;
}
std::cout << ans << "\n";
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 136ms
memory: 133080kb
input:
10 1 2 3 4 5 6 7 8 9 10
output:
0 6 20 62 140 306 536 938 1492 2306
result:
ok 10 lines
Test #2:
score: 0
Accepted
time: 135ms
memory: 132880kb
input:
100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
output:
0 6 20 62 140 306 536 938 1492 2306 3296 4722 6460 8830 11568 14946 18900 23926 29544 36510 44388 53586 63648 75674 88948 104374 121032 139966 160636 184466 209944 239050 270588 305478 342480 383370 427020 475830 527280 583338 642900 708798 777912 854022 934604 21071 111365 209991 313609 425767 5425...
result:
ok 100 lines
Test #3:
score: 0
Accepted
time: 123ms
memory: 134160kb
input:
1000 999000 999001 999002 999003 999004 999005 999006 999007 999008 999009 999010 999011 999012 999013 999014 999015 999016 999017 999018 999019 999020 999021 999022 999023 999024 999025 999026 999027 999028 999029 999030 999031 999032 999033 999034 999035 999036 999037 999038 999039 999040 999041 9...
output:
546070 193945 346418 377018 37466 751815 955839 157887 339995 522058 582121 473366 340311 290383 918701 862726 444011 438858 911955 921485 301270 699249 433065 907182 40424 772622 357721 211889 575810 629609 30983 876744 264169 808803 188203 748204 392664 267459 919490 320743 3927 490236 833633 9156...
result:
ok 1000 lines
Test #4:
score: 0
Accepted
time: 124ms
memory: 133308kb
input:
1000 453972 516606 570567 374049 422559 197777 181774 541268 5455 532617 559307 552527 174796 106684 506191 654637 48814 772908 150793 871094 187337 630103 682078 590953 456679 32784 755725 312523 235515 810164 520456 642283 616498 185466 836147 831550 261713 127618 85181 923213 33952 867185 130882 ...
output:
521457 552203 362377 520340 271000 96956 991169 901031 375542 93773 236463 744764 604355 557256 117961 512339 574575 562694 659733 287701 110161 860510 650908 740606 323739 321423 978238 159053 556787 24079 504173 566425 693719 158187 732866 614438 684481 821497 720603 866172 997262 403230 732268 82...
result:
ok 1000 lines
Test #5:
score: 0
Accepted
time: 120ms
memory: 133416kb
input:
1000 746388 708028 258366 416454 498990 90616 45928 840954 771202 75901 201827 663367 302208 908508 491895 856966 656450 563176 794405 140655 780889 646713 471035 308676 33396 438704 58210 809605 888367 100839 316212 881395 877323 45138 850544 797210 40000 440819 794639 926781 460222 17291 226354 85...
output:
825131 100250 25349 910410 710624 369637 98838 949978 409802 983803 854332 75645 843457 396665 430341 743675 571733 983824 436291 699539 760039 176823 176085 737980 434777 840310 60100 384098 799468 967137 537714 659755 4153 949560 897417 848197 489161 905487 914244 10800 753864 311218 179848 316220...
result:
ok 1000 lines
Test #6:
score: 0
Accepted
time: 135ms
memory: 134184kb
input:
1000 80775 511476 672923 825999 827426 482347 497984 568943 798803 166491 938151 14447 501355 423281 465997 297312 34439 824488 968980 467674 513959 242596 915128 822510 541867 211231 704722 824306 88541 770898 771094 312857 192490 907310 491183 24385 168119 698832 437638 305360 425730 330313 57684 ...
output:
431698 650163 625836 669564 562886 83648 181374 120479 251594 603609 325264 249583 379375 251675 181237 627004 45958 639029 636613 518362 853345 477236 17135 341433 163255 961849 207864 706325 253265 435180 997239 690726 763725 684994 682307 253163 219348 467170 997646 608245 648427 889917 626905 41...
result:
ok 1000 lines
Test #7:
score: 0
Accepted
time: 123ms
memory: 133320kb
input:
1000 9999000 9999001 9999002 9999003 9999004 9999005 9999006 9999007 9999008 9999009 9999010 9999011 9999012 9999013 9999014 9999015 9999016 9999017 9999018 9999019 9999020 9999021 9999022 9999023 9999024 9999025 9999026 9999027 9999028 9999029 9999030 9999031 9999032 9999033 9999034 9999035 9999036...
output:
678165 587960 566890 956174 697748 86527 226684 988507 787756 611376 969984 3498 821943 492596 818008 442858 366965 796460 151873 658416 318744 412768 63411 906506 664219 365337 535803 162829 245636 673258 548627 952301 739568 133837 162037 179254 36654 181961 196689 4292 997285 327583 631027 185992...
result:
ok 1000 lines
Test #8:
score: 0
Accepted
time: 127ms
memory: 134376kb
input:
3 1 3 2
output:
0 20 6
result:
ok 3 lines