e-olymp 6941. Сумма НОД

Задача

Для заданных $n$ натуральных чисел найдите сумму НОД (наибольших общих делителей) всех возможных пар этих чисел.

Входные данные

В первой строке задано количество тестов $n \ (1 < n < 100)$. Каждый тест состоит из одной строки и содержит количество входных чисел $m \ (1 < m < 100)$, за которым следуют $m$ натуральных чисел. Все входные числа натуральные, не превышающие $10^6.$

Выходные данные

Для каждого теста в отдельной строке вывести сумму $НОД$ всех возможных пар.

Тесты

Входные данные Выходные данные
1 3
4 10 20 30 40
3 7 5 12
3 125 15 25
70
3
35
2 2
3 12 7 8
4 5 14 25 11
6
10
3 4
4 5 6 7 8
4 8 6 2 9
3 2 15 6
5 12 25 29 19 11
7
11
6
10

Код

Решение

Алгоритм решения этой задачи очень простой: чтобы найти сумму НОД всех пар чисел в строке нужно сначала найти все сочетания по два числа из строки, потом посчитать НОД для каждой пары и сложить все НОД.

Ссылки

Related Images:

One thought on “e-olymp 6941. Сумма НОД

  1. — «выводится на экран»?! Вы так назвали стандартный поток вывода?
    — Не очень разумно дословно пересказывать человеческим языком программу на С++. Программа это наиболее точный способ описания того, что делает программа 🙂 Нужно описывать алгоритм. Я понимаю, что в вашем случае это совсем простое описание. Ну, значит повезло.
    — Если после формулы идет точка, то лучше вставить точку внутрь формулы. Иначе точка может переходить на новую строку. Ребята уже писали об этом.

Добавить комментарий