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

Материал из DISCOPAL
Перейти к: навигация, поиск

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))