Функция Эйлера
Для функция Эйлера — это количество целых , для которых . В частности, .
Для простого все целые числа от до взаимно просты с ним, поэтому . Для степени простого исключаются только числа, кратные :
Целое число взаимно просто с ровно тогда, когда ни один простой делитель его не делит.
Для каждого простого делителя исключаем его кратные. Пересечения учитывает формула включений-исключений: для любого выбранного набора различных простых делителей их произведение делит , поэтому кратных всем им чисел ровно , делённое на это произведение.
Раскрыв сумму включений-исключений, получаем
Произведение содержит каждое различное простое число только один раз. Его вклад вычисляем целочисленным обновлением
начиная с . Предыдущие обновления делят только на другие простые числа, поэтому по-прежнему делит текущий ответ.
У положительных взаимно простых множества простых делителей не пересекаются. Поэтому та же формула даёт
Для исходного значения это занимает времени и дополнительной памяти.
Инициализируем . Перебираем кандидатов в порядке возрастания. Если , то простое: каждое составное число уже было уменьшено при обработке меньшего простого делителя.
Применяем к каждому кратному , начиная с самого . Это включает обновление .
Вызываем для . После этого для ; нулевой элемент не используется. Каждый вызов заново строит таблицу.
Решето занимает времени и памяти. Каждый последующий запрос — обращение к таблице за .
Для каждого делителя числа объединим в группу целые , для которых .
Запишем . Тогда и , поэтому в этой группе чисел. Группы разбивают все чисел, что даёт
Для отрезка , где , храним для каждого из отрезка ответ и оставшееся значение .
Последний остаток — простое число, потому что список базовых простых покрывает все возможные маленькие делители. Каждое различное простое число вносит вклад ровно один раз, поэтому .
Начинаем обход кратных с . Включаем само , если оно лежит в отрезке, так как для его функции Эйлера тоже нужен вклад этого простого.
Два массива для отрезка занимают памяти, где . Подготовка базовых простых решетом добавляет памяти.
#include <bits/stdc++.h>
using namespace std;
long long phi(long long n) {
long long res = n;
for (long long p = 2; p <= n / p; p += (p == 2 ? 1 : 2)) {
if (n % p == 0) {
res -= res / p;
while (n % p == 0) {
n /= p;
}
}
}
if (n > 1) {
res -= res / n;
}
return res;
}
vector<int> t;
void phi_sieve(int n) {
t.resize(n + 1);
for (int x = 0; x <= n; x++) {
t[x] = x;
}
for (int p = 2; p <= n; p++) {
if (t[p] != p) {
continue;
}
for (int x = p; x <= n; x += p) {
t[x] -= t[x] / p;
}
}
}