Submission #16879653

Source Code Expand

N=int(input())

# 約数の個数のテーブルを O(N loglog N) で作る
div = [1] * (N+1)
div[0] = 0

for p in range(2, N+1):
  if div[p] != 1:
    continue
  # p は素数
  pp = p  # power of p
  e = 1
  while pp <= N:
    for n in range(pp, N+1, pp):
      div[n] += div[n] // e
    e += 1
    pp *= p  

ans = sum(div[:N])
print(ans)

Submission Info

Submission Time
Task C - A x B + C
User maspy
Language Python (3.8.2)
Score 300
Code Size 360 Byte
Status AC
Exec Time 874 ms
Memory 24732 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 300 / 300
Status
AC × 3
AC × 37
Set Name Test Cases
Sample 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt
All 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt, 01-small-01.txt, 01-small-02.txt, 01-small-03.txt, 01-small-04.txt, 01-small-05.txt, 01-small-06.txt, 01-small-07.txt, 01-small-08.txt, 01-small-09.txt, 01-small-10.txt, 02-min-01.txt, 03-random-01.txt, 03-random-02.txt, 03-random-03.txt, 03-random-04.txt, 03-random-05.txt, 05-highly-composite-number-01.txt, 05-highly-composite-number-02.txt, 05-highly-composite-number-03.txt, 05-highly-composite-number-04.txt, 05-highly-composite-number-05.txt, 06-highly-composite-number-01.txt, 06-highly-composite-number-02.txt, 06-highly-composite-number-03.txt, 06-highly-composite-number-04.txt, 06-highly-composite-number-05.txt, 07-highly-composite-number-01.txt, 07-highly-composite-number-02.txt, 07-highly-composite-number-03.txt, 07-highly-composite-number-04.txt, 07-highly-composite-number-05.txt, 08-max-01.txt, 08-max-02.txt, 08-max-03.txt
Case Name Status Exec Time Memory
00-sample-01.txt AC 26 ms 8900 KiB
00-sample-02.txt AC 28 ms 9016 KiB
00-sample-03.txt AC 874 ms 24560 KiB
01-small-01.txt AC 29 ms 8908 KiB
01-small-02.txt AC 23 ms 9016 KiB
01-small-03.txt AC 26 ms 9104 KiB
01-small-04.txt AC 31 ms 9204 KiB
01-small-05.txt AC 33 ms 8908 KiB
01-small-06.txt AC 27 ms 9132 KiB
01-small-07.txt AC 30 ms 9200 KiB
01-small-08.txt AC 21 ms 9064 KiB
01-small-09.txt AC 23 ms 9068 KiB
01-small-10.txt AC 34 ms 9012 KiB
02-min-01.txt AC 27 ms 9064 KiB
03-random-01.txt AC 103 ms 10584 KiB
03-random-02.txt AC 714 ms 22520 KiB
03-random-03.txt AC 267 ms 13964 KiB
03-random-04.txt AC 120 ms 10520 KiB
03-random-05.txt AC 48 ms 9092 KiB
05-highly-composite-number-01.txt AC 606 ms 19908 KiB
05-highly-composite-number-02.txt AC 559 ms 19284 KiB
05-highly-composite-number-03.txt AC 470 ms 17276 KiB
05-highly-composite-number-04.txt AC 105 ms 10412 KiB
05-highly-composite-number-05.txt AC 46 ms 9096 KiB
06-highly-composite-number-01.txt AC 599 ms 20220 KiB
06-highly-composite-number-02.txt AC 586 ms 19428 KiB
06-highly-composite-number-03.txt AC 466 ms 17396 KiB
06-highly-composite-number-04.txt AC 108 ms 10516 KiB
06-highly-composite-number-05.txt AC 46 ms 9092 KiB
07-highly-composite-number-01.txt AC 599 ms 20072 KiB
07-highly-composite-number-02.txt AC 556 ms 19232 KiB
07-highly-composite-number-03.txt AC 440 ms 17264 KiB
07-highly-composite-number-04.txt AC 105 ms 10568 KiB
07-highly-composite-number-05.txt AC 45 ms 9088 KiB
08-max-01.txt AC 835 ms 24396 KiB
08-max-02.txt AC 846 ms 24732 KiB
08-max-03.txt AC 866 ms 24516 KiB