- 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
- 70 lines of Python from the credited upstream file abc280_d.py.
- The implementation visibly relies on hash 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 4def run_prime_factorization(max_number: int) -> dict:5 '''Run prime factorization.6 Args:7 max_number: Int of number (greater than 1).8 Returns:9 A dictionary's items ((base, exponent) pairs).10 Landau notation: O(log n)11 '''12 13 from math import sqrt14 15 ans = dict()16 remain = max_number17 18 for base in range(2, int(sqrt(max_number)) + 1):19 if remain % base == 0:20 exponent_count = 021 22 while remain % base == 0:23 exponent_count += 124 remain = base25 26 ans[base] = exponent_count27 28 if remain != 1:29 ans[remain] = 130 31 return ans32 33 34def ok(n, prime_factorization):35 for prime, prime_count in prime_factorization:36 m, count = n, 037 38 while m > 0:39 count += m prime40 m = prime41 42 if count < prime_count:43 return False44 45 return True46 47 48def main():49 import sys50 51 input = sys.stdin.readline52 53 k = int(input())54 ps = run_prime_factorization(k).items()55 wa, ac = 1, k56 57 while ac - wa > 1:58 wj = (ac + wa) 259 60 if ok(wj, ps):61 ac = wj62 else:63 wa = wj64 65 print(ac)66 67 68if __name__ == "__main__":69 main()70