結果

問題 No.917 Make One With GCD
コンテスト
ユーザー tpyneriver
提出日時 2019-11-07 20:12:38
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 891 bytes
コンパイル時間 790 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 1,691,392 KB
最終ジャッジ日時 2024-09-15 00:43:05
合計ジャッジ時間 7,515 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other MLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
readline = sys.stdin.readline

def divi(n):
    res = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            res.append(i)
            if i != n // i:
                res.append(n//i)
    return res

from collections import Counter
Ma = 10**8 + 2
prime = [0]*Ma
for i in range(2, Ma):
    if prime[i]:
        continue
    for j in range(i, Ma, i):
        if not prime[j]:
            prime[j] = i

def pd(x):
    C = Counter()
    while x > 1:
        C[prime[x]] += 1
        x //= prime[x]
    return C


N = int(readline())
A = list(map(int, readline().split()))

divis = set()

for a in A:
    divis |= set(divi(a))

divis = list(divis)

print(divis)
res = 0
for d in divis:
    C = pd(d)
    if any(1 < c for c in C.values()):
        continue
    
    cnt = sum(1 for a in A if a % d == 0)
    
    res += (-1)**len(C) * (pow(2, cnt) - 1)

print(res)
0