Сума НСД (Розбір)

Для кожного тесту занесемо набір вхідних чисел у масив $mas$. Далі для кожної пари (i, j)~(0 \le i < j < m) обчислюємо НОД(mas[i], mas[j]) і додаємо його до загальної суми.

Приклад

Для третього прикладу відповідь дорівнює

Реалізація алгоритму

Вхідні числа зберігаємо у масиві $m$.

#define MAX 110
int m[MAX];

Функція gcd повертає найбільший спільний дільник чисел $a$ і $b$.

int gcd(int a, int b)
{
  return (!b) ? a : gcd(b, a % b);
}

Основна частина програми. Читаємо кількість тестів $tests$.

scanf("%d", &tests);
while (tests--)
{

Читаємо вхідні дані для кожного тесту.

  scanf("%d", &n);
  for (i = 0; i < n; i++)
    scanf("%d", &m[i]);

В змінній $res$ підраховуємо потрібну суму.

  res = 0;

Перебираємо всі можливі пари індексів $(i,j)$ таких що 0 \le i < j < n, для кожної пари обчислюємо НОД(m[i], m[j]) і додаємо це значення до $res$.

  for (i = 0; i < n; i++)
  for (j = i + 1; j < n; j++)
    res += gcd(m[i], m[j]);

Виводимо відповідь.

  printf("%d\n", res);
}

Python реалізація

Читаємо кількість тестів $tests$.

tests = int(input())

Читаємо вхідні дані для кожного тесту.

for _ in range(tests):
  n, *lst = list(map(int, input().split()))

В змінній $res$ підраховуємо потрібну суму.

  res = 0

Перебираємо всі можливі пари індексів $(i,j)$ таких що 0 \le i < j < n, для кожної пари обчислюємо НОД(m[i], m[j]) і додаємо це значення до $res$.

  for i in range(n):
    for j in range(i + 1, n):
      res += math.gcd(lst[i], lst[j])

Виводимо відповідь.

  print(res)