結果
問題 |
No.826 連絡網
|
ユーザー |
![]() |
提出日時 | 2025-03-31 17:28:40 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 243 ms / 2,000 ms |
コード長 | 2,037 bytes |
コンパイル時間 | 172 ms |
コンパイル使用メモリ | 82,896 KB |
実行使用メモリ | 133,456 KB |
最終ジャッジ日時 | 2025-03-31 17:30:16 |
合計ジャッジ時間 | 4,821 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
from bisect import bisect_right from collections import deque def main(): import sys input = sys.stdin.read().split() n = int(input[0]) p = int(input[1]) if p == 1: print(1) return # Sieve of Eratosthenes to generate primes up to n def sieve(max_num): if max_num < 2: return [] sieve = [True] * (max_num + 1) sieve[0] = sieve[1] = False for i in range(2, int(max_num ** 0.5) + 1): if sieve[i]: sieve[i*i : max_num + 1 : i] = [False] * len(sieve[i*i : max_num + 1 : i]) primes = [i for i, is_prime in enumerate(sieve) if is_prime] return primes primes = sieve(n) if not primes: print(1 if p == 1 else 0) return # Factorize p to get initial primes def factorize(num): factors = {} if num == 1: return factors i = 2 while i * i <= num: while num % i == 0: factors[i] = factors.get(i, 0) + 1 num = num // i i += 1 if num > 1: factors[num] = 1 return factors.keys() initial_factors = factorize(p) primes_set = set(primes) initial_primes = [prime for prime in initial_factors if prime in primes_set] if not initial_primes: print(1) return primes_sorted = primes visited = set(initial_primes) queue = deque(initial_primes) while queue: current_p = queue.popleft() max_q = n // current_p idx = bisect_right(primes_sorted, max_q) for q in primes_sorted[:idx]: if q not in visited: visited.add(q) queue.append(q) # Mark all multiples of visited primes marked = [False] * (n + 1) for prime in visited: for multiple in range(prime, n + 1, prime): marked[multiple] = True count = sum(marked) print(count) if __name__ == '__main__': main()