結果
問題 | No.1036 Make One With GCD 2 |
ユーザー |
|
提出日時 | 2020-04-24 23:01:49 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 620 bytes |
コンパイル時間 | 182 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 197,244 KB |
最終ジャッジ日時 | 2024-11-07 10:41:51 |
合計ジャッジ時間 | 18,795 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 34 TLE * 1 -- * 6 |
ソースコード
INF = 10 ** 9MOD = 10 **9 + 7import syssys.setrecursionlimit(100000000)dy = (-1,0,1,0)dx = (0,1,0,-1)from math import gcdfrom collections import defaultdictfrom copy import deepcopydef main():n = int(input())a = list(map(int,input().split()))if a[0] == 1:ans = 1else:ans = 0dp1 = defaultdict(int)dp1[a[0]] = 1for i in range(1,n):dp2 = defaultdict(int)for k in dp1:g = gcd(k,a[i])dp2[g] += dp1[k]dp2[a[i]] += 1dp1 = dp2ans += dp1[1]print(ans)if __name__=='__main__':main()