ABC400Eを解いた【エラトステネスの篩、二分探索】

筆者はレート800前後の茶～緑コーダ

ABC当日にACできなかったE問題を解いていく

実装コード

400 numberの条件は平方数であることがポイントらしい。

$10^6$ 以下の素数を適当にエラトステネスの篩で出して、そこから素因数が2つの整数のみを出す。
あとはほしい数を二分探索で探せばOK

main.py

from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table


def main():
    Q = rI()
    A = [rI() for _ in range(Q)]
    M = 10**6+1
    _, P = sieve(M)
    d = defaultdict(lambda: 0)
    for p in P:
        q = p
        while q <= M:
            d[q] += 1
            q += p
    D = [x**2 for x,c in d.items() if c == 2]
    D.sort()
    for a in A:
        i = bisect_left(D,a+1)
        print(D[i-1])
        

if __name__ == '__main__':
    main()

まとめ

平方数であるという特徴をだして
Nの最大値を減らすという発想は参考になった。