- 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
- 101 lines of Python from the credited upstream file abc300_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 3 4class Prime:5 '''Represents a snippet for prime numbers.6 '''7 8 def __init__(self, number):9 self.number = number10 self._values = []11 12 def is_included(self) -> bool:13 '''Determine whether it is a prime number.14 Args:15 number: Int of number (greater than 0).16 Returns:17 True if the input number was prime.18 False if the input number was not prime.19 See:20 https:qiita.com/srtk86/items/874639e361917e5016d421 https:docs.python.org/ja/3/library/2to3.html?highlight=isinstance22 '''23 24 from math import sqrt25 26 if (self.number <= 1) or (isinstance(self.number, float)):27 return False28 29 for i in range(2, int(sqrt(self.number)) + 1):30 if self.number % i == 0:31 return False32 33 return True34 35 def generate(self) -> list:36 '''Generate a list of prime numbers using sieve of Eratosthenes.37 Returns:38 A list of prime numbers that is eqaul to or less than the input39 number.40 Landau notation: O(n log log n)41 See:42 https:beta.atcoder.jp/contests/abc110/submissions/325494743 '''44 45 if self._values:46 return self._values47 48 is_met = [True for _ in range(self.number + 1)]49 is_met[0] = False50 is_met[1] = False51 52 for i in range(2, self.number + 1):53 if is_met[i]:54 self._values.append(i)55 56 for j in range(2 * i, self.number + 1, i):57 is_met[j] = False58 return self._values59 60 61def main():62 import sys63 64 input = sys.stdin.readline65 66 n = int(input())67 upper = 10 ** 668 p = Prime(upper)69 inf = 10 ** 1570 ps = [0] + p.generate() + [inf]71 m = len(ps)72 73 ans = 074 75 for i in range(1, m + 1):76 a = ps[i]77 a2 = a ** 278 79 if a2 > n:80 break81 82 for j in range(i + 1, m + 1):83 b = ps[j]84 85 if a2 * b > n:86 break87 88 for k in range(j + 1, m + 1):89 c = ps[k]90 91 if a2 * b * (c ** 2) > n:92 break93 94 ans += 195 96 print(ans)97 98 99if __name__ == "__main__":100 main()101