Задачи
НОД Экстрим 2
НОД Экстрим 2
По заданному значению n вычислить значение G, где
G = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} GCD(i,j)
Через 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);
Входные данные
Состоит из не более чем 20000 строк. Каждая строка содержит одно натуральное число n~(1 < n \le 4 \cdot 10^6). Последняя строка содержит n = 0 и не обрабатывается.
Выходные данные
Для каждого входного значения n вывести в отдельной строке соответствующее значение G. Значение G помещается в 64-битовое знаковое целое число.
Пример
Входные данные #1
6 10 100 200000 0
Выходные данные #1
20 67 13015 143295493160