НОД
По заданному значению n вычислить значение G, где
Через GCD(i, j) обозначен наибольший общий делитель целых чисел i и j.
Для тех, кто не встречался со знаком суммирования объясняем, что значение G формально по приведённой формуле вычисляется при помощи следующего кода:
| G=0; for(i=1; i < n;i++) for(j=i+1;j<=n;j++) { G+=GCD(i,j); } /* Здесь GCD() обозначает функцию нахождения наибольшего общего делителя двух чисел */ |
Технические условия
Входные данные
Входной файл состоит не более чем из 100 строк. Каждая строка содержит единственное натуральное число n (1 < n < 501). Последняя строка содержит n = 0 и не обрабатывается.
Выходные данные
Для каждого входного значения n вывести в отдельной строке соответствующее значение G.
Информация о задаче
Лимит времени: 2 секундыЛимит памяти: 64 MB
Баллы за пройденный тест: 10
Сложность: 13% 228/262
Классификация: Теория чисел, НОД, НОК
Пример
Пример входных данных10 100 500 0 |
Пример выходных данных67 13015 442011 |
| ← Нечестный дележ | Список задач | НОД Экстрим → |