結果

問題 No.826 連絡網
ユーザー lam6er
提出日時 2025-03-20 20:39:39
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,303 bytes
コンパイル時間 172 ms
コンパイル使用メモリ 82,448 KB
実行使用メモリ 83,792 KB
最終ジャッジ日時 2025-03-20 20:40:00
合計ジャッジ時間 3,652 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(1 << 25)

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    P = int(data[1])
    
    if P == 1:
        print(1)
        return
    
    # Step 1: SPF (Smallest Prime Factor) table
    max_n = N
    spf = list(range(max_n + 1))
    for i in range(2, int(max_n ** 0.5) + 1):
        if spf[i] == i:
            for j in range(i * i, max_n + 1, i):
                if spf[j] == j:
                    spf[j] = i
    
    # Step 2: Factorize P to get primes_p
    def get_primes(x):
        primes = set()
        while x > 1:
            p = spf[x]
            primes.add(p)
            while x % p == 0:
                x //= p
        return primes
    
    primes_p = get_primes(P)
    if not primes_p:
        print(1)
        return
    
    # Step 3: Collect all primes up to N
    primes = []
    is_prime = [False] * (max_n + 1)
    for i in range(2, max_n + 1):
        if spf[i] == i:
            primes.append(i)
            is_prime[i] = True
    
    prime_to_idx = {p: i for i, p in enumerate(primes)}
    size = len(primes)
    
    # Initialize Union-Find
    parent = list(range(size))
    
    def find(u):
        while parent[u] != u:
            parent[u] = parent[parent[u]]
            u = parent[u]
        return u
    
    def union(u, v):
        u_root = find(u)
        v_root = find(v)
        if u_root != v_root:
            parent[v_root] = u_root
    
    # Step 4: Process all x >=2 to union their prime factors
    for x in range(2, max_n + 1):
        factors = set()
        tmp = x
        while tmp > 1:
            p = spf[tmp]
            factors.add(p)
            while tmp % p == 0:
                tmp //= p
        factors = list(factors)
        if len(factors) < 1:
            continue
        # Union all factors with the first one
        first = prime_to_idx[factors[0]]
        for p in factors[1:]:
            idx = prime_to_idx[p]
            union(first, idx)
    
    # Step 5: Find the root of primes_p[0]
    target_p = next(iter(primes_p))
    target_idx = prime_to_idx[target_p]
    root = find(target_idx)
    
    # Collect all primes in the same group
    group_primes = []
    for i in range(size):
        if find(i) == root:
            group_primes.append(primes[i])
    
    # If no primes, output 1 (P itself)
    if not group_primes:
        print(1)
        return
    
    # Step 6: Inclusion-Exclusion for group_primes
    from itertools import combinations
    def inclusion_exclusion(primes_list, N):
        n = len(primes_list)
        total = 0
        for mask in range(1, 1 << n):
            bits = bin(mask).count('1')
            product = 1
            for i in range(n):
                if mask & (1 << i):
                    product *= primes_list[i]
                    if product > N:
                        product = 0
                        break
            if product == 0:
                continue
            if bits % 2 == 1:
                total += N // product
            else:
                total -= N // product
        return total
    
    count = inclusion_exclusion(group_primes, N)
    # Check if P=1 or not. Here, P >=2, so add P if needed?
    print(count)
    
if __name__ == '__main__':
    main()
0