ABC383 復習 (D) python

はじめに

ABC383の復習メモです。
A,Bがちょっと重めでしたね。Bは時間を取られました。
今回の復習対象はDのみです。

D - 9 Divisors

使用言語：Python (PyPy 3.10-v7.3.12)

説明

公式解説の通りです
解き方よりもp^8のパターンと、p^2*q^2のパターンに気づけるかという問題に感じました
9 = 1 * 9 か 9 = 3 * 3しかないので、N = p^8 or N = p^2 * q^2を考えるという発想ですね

p^2 * q^2のパターンについては、尺取り法でも2分探索（コメントアウト部）でも十分求まります

コード全文

import math
import sys

input = sys.stdin.readline


def main():
    N = input_to_int()

    prime_number = sieve_of_eratosthenes(math.isqrt(N))
    ans = 0

    # p^8パターン
    i = 0
    while i < len(prime_number) and prime_number[i] ** 8 <= N:
        ans += 1
        i += 1

    # p^2 * q^2パターン
    prime_number_sqrt = [p * p for p in prime_number]
    right = len(prime_number_sqrt) - 1
    for left in range(len(prime_number_sqrt)):
        if prime_number_sqrt[left] > N // prime_number_sqrt[left]:
            break
        while right > i and prime_number_sqrt[left] * prime_number_sqrt[right] > N:
            right -= 1
        if right <= left:
            break
        ans += right - left
    """
    # 2分探索
    from bisect import bisect_right
    for i in range(len(prime_number_sqrt)):
        if prime_number_sqrt[i] > N // prime_number_sqrt[i]:
            break
        j = bisect_right(prime_number_sqrt, N // prime_number_sqrt[i]) - 1
        ans += j - i    
    """
    print(ans)


def sieve_of_eratosthenes(x):
    # Trueなら素数候補
    is_prime = [True] * (x + 1)
    is_prime[0] = False
    is_prime[1] = False

    limit = int(x**0.5)
    for i in range(2, limit + 1):
        if is_prime[i]:
            # i*iから開始して、i毎にFalse
            for j in range(i * i, x + 1, i):
                is_prime[j] = False

    # Trueなインデックスが素数
    return [p for p, prime in enumerate(is_prime) if prime]


def input_to_int():
    return int(input())


if __name__ == "__main__":
    main()