結果
問題 | No.1653 Squarefree |
ユーザー |
|
提出日時 | 2024-05-01 15:01:18 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,965 ms / 2,000 ms |
コード長 | 970 bytes |
コンパイル時間 | 206 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 46,932 KB |
最終ジャッジ日時 | 2024-11-21 19:53:40 |
合計ジャッジ時間 | 66,036 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
from math import isqrtimport numpy as npceil_sq = lambda n: 1 + isqrt(n - 1)L, R = map(int, input().split())res = np.ones(R - L + 1, dtype=bool)def primes_np(n):is_prime = np.ones(n + 1, dtype=bool)is_prime[0] = Falseis_prime[1] = Falsefor i in range(2, int(n**0.5) + 1):if not is_prime[i]:continueis_prime[i * 2 : n + 1 : i] = Falsereturn np.where(is_prime)[0].tolist()# 10^6以下の素数の2乗で割り切れるかどうかを調べるfor p in primes_np(10**6 + 1):p2 = p**2res[((L - 1) // p2) * p2 + p2 - L : R - L + 1 : p2] = False# 10^6~10^9の素数の2乗で割り切れるかどうかを調べるfor i in range(1, 10**6 + 1):if L < i:breakl_sqrt = ceil_sq(L // i)r_sqrt = isqrt(R // i)for n in range(l_sqrt, r_sqrt + 1):if n <= 1:continueif L <= i * n**2 <= R:res[i * n**2 -L] = Falseprint(res.sum())