結果

問題 No.1653 Squarefree
ユーザー lam6er
提出日時 2025-03-31 17:41:01
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,190 bytes
コンパイル時間 167 ms
コンパイル使用メモリ 83,024 KB
実行使用メモリ 122,868 KB
最終ジャッジ日時 2025-03-31 17:42:54
合計ジャッジ時間 10,294 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math
import sys

def sieve(n):
    """Generate list of primes up to n using the Sieve of Eratosthenes."""
    sieve = [True] * (n + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(math.isqrt(n)) + 1):
        if sieve[i]:
            sieve[i*i : n+1 : i] = [False] * len(sieve[i*i : n+1 : i])
    primes = [i for i, is_p in enumerate(sieve) if is_p]
    return primes

def is_prime(n):
    """Check if n is a prime using the Miller-Rabin test with deterministic bases for n < 2^64."""
    if n <= 1:
        return False
    elif n <= 3:
        return True
    elif n % 2 == 0:
        return False
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    bases = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    for a in bases:
        if a >= n:
            continue
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def main():
    L, R = map(int, sys.stdin.readline().split())
    size = R - L + 1
    is_square_free = [True] * size  # Initialize all as square-free

    # Step 1: Mark multiples of squares of small primes (<= 1e6)
    max_prime = math.isqrt(R)
    sieve_limit = min(max_prime, 10**6)
    primes = sieve(sieve_limit)

    for p in primes:
        p_squared = p * p
        if p_squared > R:
            continue

        # Find the first occurrence of p^2 multiple >= L
        first = L + (p_squared - L % p_squared) % p_squared
        if first > R:
            continue

        # Mark all multiples in the range [first, R]
        for x in range(first, R + 1, p_squared):
            is_square_free[x - L] = False

    # Step 2: Check for numbers that are squares of primes larger than sieve_limit
    for x in range(L, R + 1):
        idx = x - L
        if not is_square_free[idx]:
            continue
        s = math.isqrt(x)
        if s * s == x and is_prime(s):
            is_square_free[idx] = False

    # Count the remaining square-free numbers
    print(sum(is_square_free))

if __name__ == "__main__":
    main()
0