結果
問題 | No.1036 Make One With GCD 2 |
ユーザー |
![]() |
提出日時 | 2020-04-24 22:21:42 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 761 bytes |
コンパイル時間 | 486 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 190,804 KB |
最終ジャッジ日時 | 2024-11-07 02:38:01 |
合計ジャッジ時間 | 22,286 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 22 WA * 19 |
ソースコード
def gcd(a: int, b: int) -> int:"""a, bの最大公約数(greatest common divisor: GCD)を求める計算量: O(log(min(a, b)))"""if b == 0:return areturn gcd(b, a%b)def multi_gcd(array: list) -> int:"""arrayのGCDを求める"""n = len(array)ans = array[0]for i in range(1, n):ans = gcd(ans, array[i])return ansn = int(input())a = list(map(int, input().split()))l, r = 0, 0ans = 0while True:tmp = a[l]while True:if r == n:breakif gcd(tmp, a[r]) == 1:ans += n - rbreakelse:tmp = gcd(tmp, a[r])r += 1l += 1if l > r:r = lif l == n:breakprint(ans)