結果

問題 No.917 Make One With GCD
ユーザー lam6er
提出日時 2025-03-20 20:42:44
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 56 ms / 2,000 ms
コード長 1,745 bytes
コンパイル時間 151 ms
コンパイル使用メモリ 82,180 KB
実行使用メモリ 66,020 KB
最終ジャッジ日時 2025-03-20 20:42:59
合計ジャッジ時間 2,947 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from math import gcd
from functools import reduce
from collections import defaultdict

def compute_gcd(arr):
    return reduce(lambda x, y: gcd(x, y), arr)

def get_prime_factors(num):
    factors = set()
    if num == 1:
        return factors
    # Process even factors
    if num % 2 == 0:
        factors.add(2)
        while num % 2 == 0:
            num //= 2
    # Process odd factors
    i = 3
    while i * i <= num:
        if num % i == 0:
            factors.add(i)
            while num % i == 0:
                num //= i
        i += 2
    # Process remaining factor
    if num > 1:
        factors.add(num)
    return factors

def main():
    input = sys.stdin.read().split()
    n = int(input[0])
    arr = list(map(int, input[1:n+1]))
    
    # Check overall GCD
    overall_gcd = compute_gcd(arr)
    if overall_gcd != 1:
        print(0)
        return
    
    # Initialize structures to track divisors and their properties
    d_to_k = dict()
    cnt = defaultdict(int)
    
    for num in arr:
        primes = get_prime_factors(num)
        m = len(primes)
        primes_list = list(primes)
        # Generate all subsets of primes to form divisors
        for mask in range(1 << m):
            d = 1
            k = 0
            for j in range(m):
                if (mask >> j) & 1:
                    d *= primes_list[j]
                    k += 1
            cnt[d] += 1
            # Record the number of primes used for this divisor
            if d not in d_to_k:
                d_to_k[d] = k
    
    sum_ans = 0
    for d in cnt:
        k = d_to_k[d]
        mu = (-1) ** k
        c = cnt[d]
        sum_ans += mu * ((1 << c) - 1)
    
    print(sum_ans)

if __name__ == "__main__":
    main()
0