- 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
- 66 lines of Python from the credited upstream file arc114_a.py.
- The implementation visibly relies on sequence storage, ordered lookup.
- 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 def __init__(self, number):8 self.number = number9 self._values = []10 11 def generate(self) -> list:12 """Generate a list of prime numbers using sieve of Eratosthenes.13 Returns:14 A list of prime numbers that is eqaul to or less than the input15 number.16 Landau notation: O(n log log n)17 See:18 https:beta.atcoder.jp/contests/abc110/submissions/325494719 """20 21 if self._values:22 return self._values23 24 is_met = [True for _ in range(self.number + 1)]25 is_met[0] = False26 is_met[1] = False27 28 for i in range(2, self.number + 1):29 if is_met[i]:30 self._values.append(i)31 32 for j in range(2 * i, self.number + 1, i):33 is_met[j] = False34 35 return self._values36 37 38def main():39 from math import gcd40 import sys41 42 input = sys.stdin.readline43 44 n = int(input())45 x = list(map(int, input().split()))46 p = Prime(max(x))47 primes = p.generate()48 prime_count = len(primes)49 ans = float("inf")50 51 for bit in range(1, 1 << prime_count):52 y = 153 54 for i in range(prime_count):55 if bit & (1 << i):56 y *= primes[i]57 58 if all(gcd(y, xi) > 1 for xi in x):59 ans = min(ans, y)60 61 print(ans)62 63 64if __name__ == "__main__":65 main()66