e-olymp
Məsələlər

НОД Экстрим

НОД Экстрим

По заданному n вычислить значение G, где

prb1146

Через 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() вычисляет наибольший общий делитель двух чисел*/

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

Состоит из не более чем 20000 строк. Каждая строка содержит целое число n (1 < n < 200001). Последняя строка содержит n = 0 и не обрабатывается.

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

Для каждого входного значения n в отдельной строке вывести соответствующее значение G. Значение G помещается в 64-битовое знаковое целое число.

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri
10
100             
20000
0
Çıxış verilənləri
67
13015
1153104356