結果
問題 | No.1653 Squarefree |
ユーザー |
|
提出日時 | 2024-05-01 14:45:58 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,120 bytes |
コンパイル時間 | 485 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 26,624 KB |
最終ジャッジ日時 | 2024-11-21 19:37:00 |
合計ジャッジ時間 | 50,075 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 WA * 9 |
ソースコード
from math import isqrtceil_sq = lambda n: 1 + isqrt(n - 1)# L <= 2x^2 <= R# 10^6 x^2 <= R# →あとは10^6までの素因数を発見すればいいL, R = map(int, input().split())res = [True] * (R - L + 1)def primes(n):is_prime = [True] * (n + 1)is_prime[0] = Falseis_prime[1] = Falsefor i in range(2, int(n**0.5) + 1):if not is_prime[i]:continuefor j in range(i * 2, n + 1, i):is_prime[j] = Falsereturn (i for i in range(n + 1) if is_prime[i])# 10^6以下の素数の2乗で割り切れるかどうかを調べるfor p in primes(10**6 + 1):p2 = p**2for i in range((L // p2) * p2 + p2, R + 1, p2):if i < L:continueres[i - L] = False# 10^6~10^9の素数の2乗で割り切れるかどうかを調べるfor i in range(1, 10**6):if L < i:breakl_sqrt = ceil_sq(L // i)r_sqrt = isqrt(R // i)for n in range(l_sqrt, r_sqrt + 1):if l_sqrt <= 1:continueif L <= i * n**2 <= R:res[i * n**2 - L] = Falseprint(res.count(True))