1147. НОД Экстрим
По заданному n вычислить значение G, где
G = 
Через НОД(i, j) обозначен наибольший общий
делитель чисел i и j.
Вход. Состоит
из не более чем 20000 строк. Каждая строка содержит целое число n (1 < n < 200001). Значение n
описано выше в условии задачи. Последняя строка содержит n = 0 и не обрабатывается.
Выход. Для каждого входного значения n в отдельной строке вывести
соответствующее значение G. Значение G помещается в 64-битовое знаковое целое
число.
Пример входа
10
100
20000
0
Пример выхода
67
13015
1153104356
РЕШЕНИЕ
теория чисел – функция Эйлера
Анализ алгоритма
Пусть d[k] = 
.
Например d[2] = 
= 
= НОД(1, 2) = 1.
Можно заметить, что
d[k] = 
= 
+ 
= d[k
– 1] +
Остается показать, как вычислять
значение быстрее обыкновенного суммирования.
Лемма. Пусть n делится на d и НОД(x, n) = d. Тогда x = dk для некоторого натурального k. А из соотношения НОД(dk, n) = d следует, что 
= 1.
Теорема. Обозначим через f(n) = 
.
Тогда f(n) = 
для всех делителей d числа n. Через 
здесь обозначена
функция Эйлера.
Доказательство. Количество таких i, для
которых НОД(i, n) = 1, равно . Количество таких i (i ≤ n), для которых НОД(i, n) = d (d делитель n, i = dk),
равно количеству таких k (k ≤ 
), для которых = 1, или 
. Значением НОД(i, n) могут быть только делители числа n. Для нахождения f(n)
остается
просуммировать значения 
по всем делителям d числа n.
Пример.
Непосредственное вычисление. f(6) = 
= НОД(1, 6) + НОД(2, 6) + НОД(3, 6)
+ НОД(4, 6) + НОД(5, 6) + НОД(6, 6) = 1 + 2 + 3 + 2 + 1 + 6 = 15.
Вычисление по формуле. f(6) = 
= 
+ 
+ 
+ 
= 
+ 
+ 
+ 
= 2 + 4 + 3 + 6 = 15.
Реализация алгоритма
Объявляем массивы. fi[i] хранит значение функции Эйлера 
.
#define MAX 200010
long long
d[MAX], fi[MAX];
Заполняем массив fi так, что fi[i] = .
void FillEuler(void)
{
memset(fi,0,sizeof(fi));
fi[1] = 1;
for(i = 2; i
< MAX; i++)
if(!fi[i])
Число i является
простым.
for(j =
i; j < MAX; j += i)
{
if(!fi[j])
fi[j] = j;
fi[j] -= fi[j]/i;
}
}
Перед вызовом функции f значения d[i] уже содержит . Тело функции f добавляет в d[j] значения так, чтобы в
конце работы функции d[j] содержало 
согласно формуле,
приведенной в теореме.
void f(void)
{
long long i;
for(i = 2; i
<= sqrt(1.0*MAX); i++)
for(j = i * i; j <
MAX; j += i)
{
Число i является делителем
j. Поэтому в d[j] следует прибавить 
. Поскольку делителем j
также является число j / i, то в d[j] следует добавить 
= 
. Если i2 = j, то к d[j] следует
прибавлять не два слагаемых, а только одно = 
.
Цикл по i достаточно
продолжать до 
, так как если i – делитель j и i >
, то с учетом того что j / i < можно утверждать, что
делитель i числа j был уже учтен когда рассматривался делитель j / i.
if (i * i
< j) d[j] += i * fi[j / i] + j / i * fi[i];
if (i * i
== j) d[j] += i * fi[i]; // i = j / i
}
}
Основная
часть программы. Инициализируем массивы.
memset(d,0,sizeof(d));
FillEuler();
for(i = 2; i < MAX; i++) d[i] =
fi[i];
|
i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
d[i] |
0 |
1 |
2 |
2 |
4 |
2 |
6 |
4 |
6 |
4 |
f();
|
i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
d[i] |
0 |
1 |
2 |
4 |
4 |
9 |
6 |
12 |
12 |
17 |
for(i = 3; i < MAX; i++)
d[i] += d[i-1];
|
i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
d[i] |
0 |
1 |
3 |
7 |
11 |
20 |
26 |
38 |
50 |
67 |
while(scanf("%lld",&n),n)
printf("%lld\n",d[n]);