結果
問題 | No.826 連絡網 |
ユーザー |
![]() |
提出日時 | 2025-01-12 21:32:25 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 598 ms / 2,000 ms |
コード長 | 588 bytes |
コンパイル時間 | 200 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 185,984 KB |
最終ジャッジ日時 | 2025-01-12 21:32:43 |
合計ジャッジ時間 | 7,958 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
def prime_factorize(n):a = set()while n % 2 == 0:a.add(2)n //= 2f = 3while f * f <= n:if n % f == 0:a.add(f)n //= felse:f += 2if n != 1:a.add(n)return aN, P = map(int,input().split())if P == 1:print(N)exit()X = [0] * (N + 1)Q = prime_factorize(P)Q2 = {1}while Q:x = Q.pop()X[x] = 1if x not in Q2:for i in range(1,N//x + 1):X[x * i] = 1if i not in Q2:Q.add(i)Q2.add(x)print(sum(X))