- Translate each rule into one explicit state update.
- Maintain the invariant after every processed item.
- Return the accumulated state once all relevant input has been handled.
Code notes
- 114 lines of Python from the credited upstream file abc383_d.py.
- The implementation visibly relies on sequence storage.
- No explicit loop blocks detected.
Complexity
Count the number and nesting of passes over the input, then include the maintained containers in the memory estimate.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
12 3from bisect import bisect_right4from typing import List5 6 7class Prime:8 """Represents a snippet for prime numbers."""9 10 def __init__(self, number):11 self.number = number12 self._values = []13 14 def is_included(self) -> bool:15 """Determine whether it is a prime number.16 17 Args:18 number: Int of number (greater than 0).19 20 Returns:21 True if the input number was prime.22 False if the input number was not prime.23 24 See:25 https:qiita.com/srtk86/items/874639e361917e5016d426 https:docs.python.org/ja/3/library/2to3.html?highlight=isinstance27 """28 29 from math import sqrt30 31 if (self.number <= 1) or (isinstance(self.number, float)):32 return False33 34 for i in range(2, int(sqrt(self.number)) + 1):35 if self.number % i == 0:36 return False37 38 return True39 40 def generate(self) -> list:41 """Generate a list of prime numbers using sieve of Eratosthenes.42 43 Returns:44 A list of prime numbers that is eqaul to or less than the input45 number.46 47 Landau notation: O(n log log n)48 49 See:50 https:beta.atcoder.jp/contests/abc110/submissions/325494751 """52 53 if self._values:54 return self._values55 56 is_met = [True for _ in range(self.number + 1)]57 is_met[0] = False58 is_met[1] = False59 60 for i in range(2, self.number + 1):61 if is_met[i]:62 self._values.append(i)63 64 for j in range(2 * i, self.number + 1, i):65 is_met[j] = False66 return self._values67 68 69def bisect_le(sorted_array: List[int], value: int):70 """Find the largest element <= x and its index, or None if it doesn't exist."""71 72 if sorted_array[0] <= value:73 index: int = bisect_right(sorted_array, value) - 174 75 return index, sorted_array[index]76 77 return None, None78 79 80def main():81 import sys82 from math import sqrt83 84 input = sys.stdin.readline85 86 n = int(input())87 m = int(sqrt(n))88 p = Prime(m)89 ps = p.generate()90 ans = 091 92 for i, pi in enumerate(ps):93 k = m pi94 95 j, _ = bisect_le(ps, k)96 97 if j is None or j < i:98 break99 100 ans += j - i101 102 for i in range(1, n + 1):103 if i**8 > n:104 break105 106 if i in ps:107 ans += 1108 109 print(ans)110 111 112if __name__ == "__main__":113 main()114