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

Код

Решение

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

Ссылки

e-olymp 7110. Весы

Задача


Измерение веса предмета осуществляется с помощью лабораторных весов. С помощью набора из $7$ гирь весом $1$ г, $3$ г, $9$ г, $27$ г, $81$ г, $243$ г и $729$ г можно измерить вес любого предмета с целым весом от $1$ до $1093$ г единственным способом. Например, для измерения предмета весом $4$ г необходимо на одну чашу положить гири в $1$ и $3$ г, а на другую сам предмет, а, скажем, для предмета весом $68$ г на чашку с ним добавляются гири в $1$, $3$ и $9$ г, а на другую — гиря в $81$ г.

Определите, сколько гирь из данного набора необходимо использовать для взвешивания предмета заданного веса.

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

Одно натуральное число $x \ (1 \leqslant x \leqslant 1000)$ — вес предмета.

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

Вывести количество гирь, необходимых для взвешивания данного предмета.

Тесты

Входные данные Выходные данные
1 4 2
2 68 4
3 27 1
4 555 5
5 1000 4

Код

Решение

Пусть предмет располагается на правой чаше весов. Тогда на левой чаше первым делом мы должны расположить ближайшую по весу гирю. Если этой гири оказывается недостаточно для уравновешивания весов, тогда мы добавляем на левую чашу еще одну гирю, вес которой будет ближе всех к разности весов на чашах. Повторяем операцию, пока чаши не уравняются. Если же вес левой чаши будет больше правой, то по такому же принципу добавляем гири на правую чашу. И с каждым добавлением гири увеличиваем счетчик, значение которого выводится при уравновешивании весов. И хоть такой ход решения не полностью удовлетворяет условию задачи, так как в некоторых случаях одни и те же гири используются дважды, тем не менее ответ всегда будет совпадать с ответом решения исходной задачи. Это было проверено с помощью сайта, который сравнил результаты работы двух программ, которые выдают все ответы моего решения и правильного.

Ссылки