結果

問題 No.1730 GCD on Blackboard in yukicoder
ユーザー lam6er
提出日時 2025-04-16 16:11:38
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,738 bytes
コンパイル時間 303 ms
コンパイル使用メモリ 81,656 KB
実行使用メモリ 134,724 KB
最終ジャッジ日時 2025-04-16 16:16:45
合計ジャッジ時間 6,875 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math
from collections import defaultdict

def main():
    input = sys.stdin.read().split()
    n = int(input[0])
    a = list(map(int, input[1:n+1]))
    
    # Compute GCD of the entire array
    current_gcd = a[0]
    for num in a[1:]:
        current_gcd = math.gcd(current_gcd, num)
    
    # Generate all divisors for each element
    divisors = defaultdict(int)
    for num in a:
        temp = set()
        for i in range(1, int(math.isqrt(num)) + 1):
            if num % i == 0:
                temp.add(i)
                temp.add(num // i)
        for d in temp:
            divisors[d] += 1
    
    # Add the GCD to the divisors if not already present (though it should be)
    divisors[current_gcd] = n  # since all elements are divisible by the GCD
    
    # Extract unique divisors and sort them in descending order
    sorted_d = sorted(divisors.keys(), reverse=True)
    
    # Precompute max_d for each x
    max_d = [0] * (n + 2)  # x ranges from 1 to N
    current_max_x = 0
    
    for d in sorted_d:
        cnt = divisors[d]
        if cnt > current_max_x:
            start = current_max_x + 1
            end = cnt
            for x in range(start, end + 1):
                if x > n:
                    break
                max_d[x] = d
            current_max_x = cnt
            if current_max_x >= n:
                break
    
    # For x beyond current_max_x, no d can satisfy, but according to problem statement, the GCD is already handled
    # Now, generate the answers for each K
    for k in range(n):
        x = n - k
        if x < 1:
            print(0)
        else:
            print(max_d[x] if max_d[x] != 0 else current_gcd)
    
if __name__ == "__main__":
    main()
0