Участник:Andriygav/ADAGF

Материал из DISCOPAL
< Участник:Andriygav
Версия от 21:46, 21 ноября 2020; Andriygav (обсуждение | вклад) (Новая страница: «https://www.spoj.com/problems/ADAGF/ <code-python> import math def solver(N, a): result = 0 lengths = dict() for item in a: new_lengths = dic…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

https://www.spoj.com/problems/ADAGF/

import math
def solver(N, a):
    result = 0
    lengths = dict()
    for item in a:
        new_lengths = dict()
        for key in lengths:
            to = math.gcd(item, key)
            if to not in new_lengths:
                new_lengths[to] = 0
            new_lengths[to] += lengths[key]
 
        if item not in new_lengths:
            new_lengths[item] = 0
        new_lengths[item] += 1
 
        lengths = new_lengths
        for key in lengths:
            result += key*lengths[key]
 
    return result
 
N = int(input())
a = list(map(int, input().split()))
print(solver(N, a))