ABC250Dを解いた

筆者はレート600前後の茶色コーダ

7/11開催のADTで登場した以下のABCの過去問題を解いていく

ADT(ALL)のページ

実装コード

$p\times q^3$ なので使う最大の素数は適当に$N^{\frac{1}{3}}$とみつもってエラトステネスのふるいをして
素数を列挙してみる。あとは素数なので組み合わせ被りを気にせず数え上げたらACした。

import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)

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():
    N = rI()

    _, primes = sieve(int(N**(1/3)))
    M = len(primes)

    ans = 0
    for i,p in enumerate(primes):
        b = ans
        for j in range(i+1,M):
            num = p * (primes[j]**3)
            if num > N:
                break
            ans += 1
        if b == ans:
            break
    print(ans)
if __name__ == '__main__':
    main()

まとめ

ABC250Dを解いた、エラトステネスのふるいを利用して素数を列挙して順番に数え上げた。

感想

この問題は解説見ずにとけた早解き寄りの問題だった。
このような問題は切り口をみつければ簡単に解けるがそれまでがなかなか大変ですね。

余談

エラトステネスのふるいってなかなか名前覚えられないの自分だけ？