結果
問題 |
No.2552 Not Coprime, Not Divisor
|
ユーザー |
![]() |
提出日時 | 2023-11-25 15:29:44 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 744 bytes |
コンパイル時間 | 547 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 43,772 KB |
最終ジャッジ日時 | 2024-09-26 10:52:36 |
合計ジャッジ時間 | 6,880 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 3 |
other | TLE * 1 -- * 24 |
ソースコード
from collections import deque def primes(n): p = [] flgs = [False]*(n+1) for i in range(2, n+1): if not flgs[i]: p.append(i) for j in range(i*2, n+1, i): flgs[j] = True return p N = int(input()) answer = 0 ps = primes(N) queue = deque([(p, i, 0) for i, p in enumerate(ps)]) while queue: now, end, count = queue.popleft() cnt = N//now if count%2 == 0: answer += cnt*(cnt-1) // 2 else: answer -= cnt*(cnt-1) // 2 for j, p in enumerate(ps[end+1:], start=end+1): if now*p > N: break queue.append((now*p, j, count+1)) for i in range(2, N+1): if N//i == 1: break answer -= (N//i)-1 print(answer)