結果

問題 No.1036 Make One With GCD 2
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:10:36
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 990 bytes
コンパイル時間 324 ms
コンパイル使用メモリ 81,968 KB
実行使用メモリ 162,952 KB
最終ジャッジ日時 2025-06-12 21:12:25
合計ジャッジ時間 18,859 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 34 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    A = list(map(int, data[1:n+1]))
    
    result = 0
    prev_list = []
    
    for num in A:
        curr_dict = {}
        # Add the current element as a single-element subarray
        if num in curr_dict:
            curr_dict[num] += 1
        else:
            curr_dict[num] = 1
        
        # Process each (g, cnt) in prev_list
        for g, cnt in prev_list:
            new_g = math.gcd(g, num)
            if new_g in curr_dict:
                curr_dict[new_g] += cnt
            else:
                curr_dict[new_g] = cnt
        
        # Check if 1 is in curr_dict
        if 1 in curr_dict:
            result += curr_dict[1]
        
        # Prepare prev_list for next iteration
        prev_list = []
        for g in curr_dict:
            prev_list.append((g, curr_dict[g]))
    
    print(result)

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