Мотивация и контекст

Представьте задачу: вычислить 2^(10^(10^10)) mod (10^9 + 9). Показатель степени невообразимо велик — он имеет миллиарды цифр. Прямое возведение в степень невозможно. Именно здесь приходит функция Эйлера: так как 10^9 + 9 простое, φ(10^9 + 9) = 10^9 + 8, и нам нужно найти (10^(10^10)) mod (10^9 + 8) — рекурсивно применяем ту же идею!

Функция Эйлера — один из центральных объектов мультипликативной теории чисел. Её связь с теоремой Эйлера (из главы 4) открывает способ «сворачивать» огромные показатели степеней. Мультипликативность функции делает её вычисление элегантно быстрым. А равенство ∑_{d|n} φ(d) = n неожиданно связывает φ с делителями.

Теория

Определение и формула Эйлера

Определение. Функция Эйлера φ(n) (также называемая «эйлеровым тотиентом») — это количество натуральных чисел от 1 до n, взаимно простых с n:

φ(n) = |{k ∈ {1, 2, …, n} : gcd(k, n) = 1}|

Примеры:

• φ(1) = 1 (только число 1 взаимно просто с 1)
• φ(2) = 1 (только 1)
• φ(6) = 2 (числа 1 и 5)
• φ(12) = 4 (числа 1, 5, 7, 11)
• φ(p) = p − 1 для простого p (все числа 1, …, p−1 взаимно просты с p)

Теорема (формула Эйлера). Для n = p₁^{a₁} · p₂^{a₂} · … · pₖ^{aₖ}:

φ(n) = n · ∏ᵢ (1 − 1/pᵢ) = n · (p₁−1)/p₁ · (p₂−1)/p₂ · … · (pₖ−1)/pₖ

Доказательство. Воспользуемся принципом включений-исключений (формула Мёбиуса). Обозначим Aᵢ — множество чисел от 1 до n, делящихся на pᵢ. Тогда:

|A₁ ∪ A₂ ∪ … ∪ Aₖ| = ∑|Aᵢ| − ∑|Aᵢ ∩ Aⱼ| + …

|Aᵢ| = n/pᵢ, |Aᵢ ∩ Aⱼ| = n/(pᵢpⱼ), и так далее (поскольку pᵢ различны).

По формуле включений-исключений:

φ(n) = n − ∑ n/pᵢ + ∑ n/(pᵢpⱼ) − … = n · ∏ᵢ (1 − 1/pᵢ)

Последнее равенство — результат раскрытия скобок в произведении.

Важные частные случаи:

• φ(pᵃ) = pᵃ − pᵃ⁻¹ = pᵃ⁻¹ · (p − 1) — для степени простого
• φ(2ᵃ) = 2ᵃ⁻¹ при a ≥ 1
• φ(mn) = φ(m) · φ(n) при gcd(m, n) = 1 — мультипликативность (доказана ниже)

Мультипликативность φ

Теорема. Если gcd(m, n) = 1, то φ(mn) = φ(m) · φ(n).

Доказательство через КТО. По Китайской теореме об остатках (глава 5), при gcd(m, n) = 1:

Z_{mn} ≅ Z_m × Z_n (изоморфизм колец)

Это изоморфизм переводит единицы в единицы: a взаимно просто с mn тогда и только тогда, когда a mod m взаимно просто с m И a mod n взаимно просто с n. Значит:

|(Z_{mn})×| = |(Z_m)×| · |(Z_n)×| φ(mn) = φ(m) · φ(n)

Альтернативное доказательство. Запишем числа от 1 до mn в таблицу m строк по n столбцов: строка i (0 ≤ i < m), столбец j (0 ≤ j < n) содержит i·n + j + 1.

Элемент взаимно прост с mn тогда и только тогда, когда он взаимно прост и с m, и с n. Для фиксированного столбца j: элементы взаимно просты с n тогда и только тогда, когда gcd(j+1, n) = 1 — таких столбцов φ(n). В каждом «хорошем» столбце: элементы образуют полную систему вычетов mod m (так как n взаимно просто с m, при изменении строки i меняется остаток mod m), поэтому ровно φ(m) из них взаимно просты с m. Итого: φ(m) · φ(n).

Сумма по делителям

Теорема. Для любого натурального n: ∑_{d|n} φ(d) = n

Доказательство. Разобьём числа {1, 2, …, n} на группы по значению gcd(k, n) = d, где d | n. Число k лежит в группе с gcd = d тогда и только тогда, когда k = d·j, gcd(j, n/d) = 1, 1 ≤ j ≤ n/d. Таких j ровно φ(n/d). Суммируя по всем делителям:

n = ∑{d|n} φ(n/d) = ∑{d|n} φ(d)

(последнее равенство — замена d ↦ n/d в сумме).

Это тождество часто используется для проверки: если вы реализовали φ, можно посчитать ∑_{d|n} φ(d) и убедиться, что получается n.

Теорема Эйлера и её применение

Напомним (из главы 4): если gcd(a, n) = 1, то a^{φ(n)} ≡ 1 (mod n).

Следствие для больших степеней. Вычислить a^b mod n при очень большом b:

• Если gcd(a, n) = 1: a^b ≡ a^{b mod φ(n)} (mod n).
• Если gcd(a, n) > 1: формула работает с оговоркой (см. раздел 6.6).

Вычисление φ(n) за O(√n)

Факторизуем n за O(√n) и применяем формулу Эйлера:

n = p₁^{a₁} · … · pₖ^{aₖ}
φ(n) = n · ∏ (1 − 1/pᵢ)

Реализация: для каждого найденного простого делителя p умножаем φ на (p−1) и делим на p.

Теорема Эйлера для больших степеней (обобщение)

Что если gcd(a, n) > 1? Тогда a^{φ(n)} ≢ 1 (mod n), и формула a^b ≡ a^{b mod φ(n)} неверна.

Теорема (обобщённая). Для любых a, b, n с b ≥ log₂ n:

a^b ≡ a^{φ(n) + (b mod φ(n))} (mod n)

Доказательство (набросок). Разложим a = ∏ pᵢ^{eᵢ}. Можно показать, что при b ≥ log₂ n показатель достаточно велик, чтобы все «общие» кратные полностью «наполнились», и начинается периодичность с периодом φ(n). Точное доказательство требует анализа p-адических валюаций.

Практическое правило: при b ≥ log₂(n) используйте b' = φ(n) + (b mod φ(n)). При b < log₂(n) прямо считайте a^b mod n.

Лестница Эйлера (итерированное применение)

«Лестница Эйлера» — метод вычисления башенных степеней: a^{a^{a^{…}}} mod n.

Ключевое наблюдение: последовательность n, φ(n), φ(φ(n)), … строго убывает и достигает 1 не более чем за O(log n) шагов. Это означает, что глубина рекурсии ограничена!

Алгоритм для вычисления a↑↑k mod n (k-кратная степенная башня a^{a^{a^{…}}}):

tower(a, k, n):
    если n == 1: вернуть 0
    если k == 0: вернуть 1 mod n
    если k == 1: вернуть a mod n
    b = tower(a, k-1, φ(n))
    если gcd(a, n) == 1: вернуть power(a, b mod φ(n), n)
    иначе: вернуть power(a, φ(n) + b mod φ(n), n)  // обобщённая формула

Почему это работает: на каждом уровне рекурсии модуль заменяется на φ от предыдущего. Цепочка n → φ(n) → φ(φ(n)) → … убывает до 1 за O(log n) шагов, так как:

• Если n чётное: φ(n) ≤ n/2
• Если n нечётное: φ(n) чётное (для n > 1), значит следующий шаг: φ(φ(n)) ≤ φ(n)/2

Итого: O(log² n) шагов до 1.

Ключевые формулы (сводка)

Реализация на C++20

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// ─────────────────────────────────────────────────────────────────
// Функция Эйлера для одного числа — O(√n)
// ─────────────────────────────────────────────────────────────────
ll euler_phi(ll n) {
    ll result = n;
    for (ll p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            result -= result / p;  // result *= (1 - 1/p) = result * (p-1)/p
        }
    }
    if (n > 1) result -= result / n;  // n — оставшийся простой делитель
    return result;
}

// ─────────────────────────────────────────────────────────────────
// Решето Эратосфена для вычисления φ(1..N) — O(N log log N)
// ─────────────────────────────────────────────────────────────────
vector<ll> euler_sieve(int N) {
    vector<ll> phi(N + 1);
    iota(phi.begin(), phi.end(), 0LL);  // phi[i] = i изначально
    for (int i = 2; i <= N; ++i) {
        if (phi[i] == i) {  // i — простое (не было пересчитано)
            for (int j = i; j <= N; j += i) {
                phi[j] -= phi[j] / i;  // phi[j] *= (1 - 1/i)
            }
        }
    }
    return phi;
}

// ─────────────────────────────────────────────────────────────────
// Линейное решето — O(N), вычисляет и φ, и список простых
// ─────────────────────────────────────────────────────────────────
pair<vector<ll>, vector<int>> linear_sieve(int N) {
    vector<ll> phi(N + 1, 0);
    vector<int> min_prime(N + 1, 0);  // наименьший простой делитель
    vector<int> primes;

    phi[1] = 1;
    for (int i = 2; i <= N; ++i) {
        if (min_prime[i] == 0) {  // i — простое
            min_prime[i] = i;
            phi[i] = i - 1;
            primes.push_back(i);
        }
        for (int p : primes) {
            if ((ll)p * i > N) break;
            min_prime[p * i] = p;
            if (i % p == 0) {
                // p | i: phi[p*i] = phi[i] * p (так как p уже в факторизации i)
                phi[p * i] = phi[i] * p;
                break;
            } else {
                // gcd(p, i) = 1: phi[p*i] = phi[p] * phi[i] = (p-1)*phi[i]
                phi[p * i] = phi[i] * (p - 1);
            }
        }
    }
    return {phi, primes};
}

// ─────────────────────────────────────────────────────────────────
// Проверка тождества sum_{d|n} phi(d) = n
// ─────────────────────────────────────────────────────────────────
bool verify_sum_identity(int n, const vector<ll>& phi) {
    ll sum = 0;
    for (int d = 1; d <= n; ++d)
        if (n % d == 0) sum += phi[d];
    return sum == n;
}

// ─────────────────────────────────────────────────────────────────
// Быстрое возведение в степень по модулю
// ─────────────────────────────────────────────────────────────────
ll power(ll base, ll exp, ll mod) {
    if (mod == 1) return 0;
    ll result = 1;
    base %= mod;
    if (base < 0) base += mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

// ─────────────────────────────────────────────────────────────────
// a^b mod n для БОЛЬШОГО b (задан как строка или рекурсивно)
// gcd(a, n) может быть > 1
// Обобщённая теорема Эйлера: a^b ≡ a^{phi(n) + b mod phi(n)} (mod n)
// при b >= log2(n)
// ─────────────────────────────────────────────────────────────────

// b задаётся как строка десятичных цифр (может быть огромным)
// Возвращает b mod m
ll big_mod(const string& b, ll m) {
    if (m == 1) return 0;
    ll result = 0;
    for (char c : b) result = (result * 10 + (c - '0')) % m;
    return result;
}

// Проверяет, b >= threshold (строка >= число)
bool big_ge(const string& b, ll threshold) {
    if ((ll)b.size() > 18) return true;  // точно больше
    ll val = 0;
    for (char c : b) {
        val = val * 10 + (c - '0');
        if (val >= threshold) return true;
    }
    return val >= threshold;
}

// a^b mod n, b задан как строка, a и n — обычные числа
ll power_big(ll a, const string& b, ll n) {
    if (n == 1) return 0;
    ll phi_n = euler_phi(n);
    ll exp;
    if (big_ge(b, (ll)log2(n) + 1)) {
        // b достаточно большой — применяем обобщённую формулу
        if (__gcd(a, n) == 1) {
            exp = big_mod(b, phi_n);
        } else {
            exp = phi_n + big_mod(b, phi_n);
        }
    } else {
        // b маленький — просто конвертируем
        exp = 0;
        for (char c : b) exp = exp * 10 + (c - '0');
    }
    return power(a, exp, n);
}

// ─────────────────────────────────────────────────────────────────
// Лестница Эйлера: a^{a^{a^{...}}} (k копий a) mod n
// Рекурсивный спуск по цепочке φ
// Сложность: O(log^2 n * log(max_val)) — O(log^3 n) с учётом power
// ─────────────────────────────────────────────────────────────────

// Возвращает {value mod n, is_large} — флаг "значение >= log2(n)"
// Флаг нужен для корректного применения обобщённой теоремы
pair<ll, bool> tower_mod(ll a, ll k, ll n) {
    if (n == 1) return {0, true};
    if (k == 0) return {1 % n, false};
    if (k == 1) {
        ll val = a % n;
        return {val, a >= (ll)log2(n) + 1};
    }
    // Рекурсивно считаем показатель mod phi(n)
    ll phi_n = euler_phi(n);
    auto [b_mod_phi, b_large] = tower_mod(a, k - 1, phi_n);

    // Флаг "b >= log2(n)" — нужен для обобщённой формулы
    // Считаем: если k >= 2 и a >= 2, то a^{a^...} >= a^2 >= 4
    // При достаточно большом k, башня точно >= log2(n)
    bool b_is_large = b_large || (k >= 2 && a >= 2 && b_mod_phi + phi_n >= (ll)log2(n) + 1);

    ll exp;
    if (b_is_large && __gcd(a % n, n) > 1) {
        exp = phi_n + b_mod_phi;
    } else {
        exp = b_mod_phi;
    }
    ll result = power(a % n, exp, n);
    return {result, true};  // башня высоты >= 2 точно большая
}

// ─────────────────────────────────────────────────────────────────
// Вычисление суммы φ(1) + φ(2) + ... + φ(n) за O(√n)
// Использует тождество ∑_{d=1}^{n} φ(d) = n(n+1)/2 - ∑_{d=2}^{n} ∑_{k=1}^{n/d} φ(k)
// (через функцию Мёбиуса, метод Люси Хеджехог / Мин-25)
// Упрощённая версия через решето для небольших n:
// ─────────────────────────────────────────────────────────────────
ll sum_phi(int N) {
    auto phi = euler_sieve(N);
    ll sum = 0;
    for (int i = 1; i <= N; ++i) sum += phi[i];
    return sum;
}

// ─────────────────────────────────────────────────────────────────
// Демонстрация
// ─────────────────────────────────────────────────────────────────
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Проверка euler_phi
    cout << "phi(12) = " << euler_phi(12) << "\n";  // 4
    cout << "phi(36) = " << euler_phi(36) << "\n";  // 12
    cout << "phi(100) = " << euler_phi(100) << "\n";  // 40

    // Проверка решета
    auto phi = euler_sieve(20);
    cout << "phi(1..20): ";
    for (int i = 1; i <= 20; ++i) cout << phi[i] << " ";
    cout << "\n";

    // Проверка тождества sum phi(d) = n
    for (int n = 1; n <= 20; ++n) {
        assert(verify_sum_identity(n, phi));
    }
    cout << "Тождество sum phi(d)=n верно для n=1..20\n";

    // Линейное решето
    auto [phi2, primes] = linear_sieve(30);
    cout << "Простые до 30: ";
    for (int p : primes) cout << p << " ";
    cout << "\n";

    // Лестница Эйлера: 2^{2^{2^2}} mod 1000000007
    auto [val, _] = tower_mod(2, 4, 1000000007LL);
    cout << "2^^4 mod 10^9+7 = " << val << "\n";  // 2^65536 mod 10^9+7

    // Сумма φ(1..100)
    cout << "sum phi(1..100) = " << sum_phi(100) << "\n";  // 3044

    return 0;
}

Анализ сложности:

Разбор задачи 1 — Степень по очень большому модулю (простая)

Условие. Вычислить a^b mod n, где a, n ≤ 10^9, а b задан как строка длиной до 10^6 цифр. (Codeforces 906D style)

Разбор. Применяем теорему Эйлера напрямую.

Алгоритм:

1. Проверяем, есть ли у b специальные случаи (b = 0, a = 0, a = 1).
2. Вычисляем φ(n) за O(√n).
3. Редуцируем b mod φ(n), обходя строку цифра за цифрой.
4. Применяем power(a, b_reduced, n).

Важная тонкость: если gcd(a, n) > 1 и b достаточно велик, используем обобщённую формулу. «Достаточно велик» означает b ≥ log₂(n) ≈ 30 для n ≤ 10^9.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll euler_phi(ll n) {
    ll result = n;
    ll orig = n;
    for (ll p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            result -= result / p;
        }
    }
    if (n > 1) result -= result / n;
    return result;
}

ll power(ll base, ll exp, ll mod) {
    if (mod == 1) return 0;
    ll result = 1; base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod; exp >>= 1;
    }
    return result;
}

int main() {
    ll a, n; string b;
    cin >> a >> b >> n;

    if (n == 1) { cout << 0; return 0; }
    if (b == "0") { cout << 1 % n; return 0; }

    ll phi_n = euler_phi(n);
    ll g = __gcd(a % n, n);

    // Редуцируем b mod phi_n
    ll b_mod = 0;
    bool b_large = b.size() > 18;  // точно >= log2(n) для n <= 10^9
    for (char c : b) {
        b_mod = (b_mod * 10 + (c - '0')) % phi_n;
    }
    if (!b_large) {
        // Пересчитаем реальное значение b для проверки
        ll bval = 0;
        bool overflow = false;
        for (char c : b) {
            if (bval > 1e18 / 10) { overflow = true; break; }
            bval = bval * 10 + (c - '0');
        }
        b_large = overflow || bval >= 30;  // log2(10^9) < 30
    }

    ll exp;
    if (g == 1) {
        exp = b_mod;  // a^b ≡ a^{b mod phi(n)} (mod n)
    } else if (b_large) {
        exp = phi_n + b_mod;  // обобщённая формула
    } else {
        // b маленький, считаем напрямую
        ll bval = 0;
        for (char c : b) bval = bval * 10 + (c - '0');
        exp = bval;
    }

    cout << power(a, exp, n) << "\n";
    return 0;
}

Проверка: a = 2, b = "1000000000000000000000000", n = 1000000007 (простое). φ(n) = 10^9 + 6. b mod φ(n) вычисляется за O(|b|). Ответ: 2^{b mod(10^9+6)} mod (10^9+7).

Разбор задачи 2 — Сумма φ по делителям с запросами (средняя)

Условие. Дано Q запросов. Для каждого n (1 ≤ n ≤ 10^6) вывести ∑_{d|n} φ(d). (Адаптация классической задачи SPOJ)

Разбор. По тождеству ∑{d|n} φ(d) = n, ответ на каждый запрос просто n! Но допустим условие усложнено: вывести ∑{d|n} φ(d²) или ∑_{d|n} d·φ(d).

Рассмотрим вариант: вывести f(n) = ∑_{d|n} φ(d) · μ(n/d), где μ — функция Мёбиуса (это диофантово обращение). Такие задачи решаются через линейное свёртывание (Dirichlet convolution).

Для варианта ∑_{d|n} φ(d) = n решение тривиально, но полезен метод предвычисления через решето:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 1'000'001;

// Предвычислить g(n) = sum_{d|n} phi(d) для всех n до N
// Используем дивизорное решето (аналог решета Эратосфена для сумм)
// Сложность: O(N log N)
vector<ll> sum_phi_divisors(int N) {
    vector<ll> phi(N+1);
    iota(phi.begin(), phi.end(), 0LL);
    for (int i = 2; i <= N; ++i)
        if (phi[i] == i)  // простое
            for (int j = i; j <= N; j += i)
                phi[j] -= phi[j] / i;

    // g(n) = sum_{d|n} phi(d) — по теореме это просто n
    // но продемонстрируем общий метод:
    vector<ll> g(N+1, 0);
    for (int d = 1; d <= N; ++d)
        for (int k = d; k <= N; k += d)
            g[k] += phi[d];
    return g;
}

// Более сложный вариант: sum_{d|n} phi(d) * mu(n/d) = [n == 1]
// (тождество для функции Мёбиуса и функции Эйлера)
// Это обращение Мёбиуса: id = phi * 1 => phi = id * mu (свёртка)

int main() {
    auto g = sum_phi_divisors(100);
    // g[n] должно равняться n по тождеству
    for (int n = 1; n <= 20; ++n)
        cout << "g(" << n << ") = " << g[n] << " (ожидается " << n << ")\n";
    return 0;
}

Реальная задача на соревнованиях. Найти ∑{i=1}^{N} ∑{j=1}^{N} gcd(i, j). Это классика, решаемая через φ:

∑{i=1}^{N} ∑{j=1}^{N} gcd(i, j) = ∑{d=1}^{N} d · |{(i,j): gcd(i,j)=d}| = ∑{d=1}^{N} d · |{(i,j): gcd(i/d, j/d)=1, i,j ≤ N}| = ∑_{d=1}^{N} d · (число пар (a,b) ≤ N/d с gcd=1)

Число пар (a,b) от 1 до m с gcd(a,b)=1: S(m) = 2·∑_{k=1}^{m} φ(k) − 1.

Если предвычислить префиксные суммы φ: P[m] = ∑_{k=1}^{m} φ(k), то ответ:

∑_{d=1}^{N} d · (2·P[N/d] − 1)

за O(N) после O(N log log N) предвычисления.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int N; cin >> N;

    // Решето для phi
    vector<ll> phi(N+1);
    iota(phi.begin(), phi.end(), 0LL);
    for (int i = 2; i <= N; ++i)
        if (phi[i] == i)
            for (int j = i; j <= N; j += i)
                phi[j] -= phi[j] / i;

    // Префиксные суммы
    vector<ll> P(N+2, 0);
    for (int i = 1; i <= N; ++i) P[i] = P[i-1] + phi[i];

    ll ans = 0;
    for (int d = 1; d <= N; ++d) {
        ll m = N / d;
        ans += (ll)d * (2 * P[m] - 1);
    }
    cout << ans << "\n";
    return 0;
}

Разбор задачи 3 — Башенная степень по модулю (Codeforces Div.1 D / ICPC уровень)

Условие. Дано a и k — вычислить a^{a^{a^{…}}} (k копий a) по модулю m = 10^9 + 7. Значения: a ≤ 10^6, k ≤ 10^{100000} (задано как строка!). (Задача уровня Codeforces 906E / IOI 2011 style)

Разбор. Это «лестница Эйлера» с дополнительным усложнением: k тоже огромное.

Основная идея:

1. Если k = 0: ответ 1 mod m.
2. Если k = 1: ответ a mod m.
3. Иначе: нужно вычислить a^{exp} mod m, где exp = a^{a^{…}} (k−1 копий).

Ключевой вопрос: как найти exp mod φ(m)?

Рекурсивно! Нам нужен exp mod φ(m), а для этого — exp mod φ(φ(m)), и т.д. Цепочка φ обрывается на 1 через O(log m) шагов.

Дополнительная сложность: k огромное (до 10^{100000} цифр). Нам нужно уметь «уменьшать» k на 1 в большом числе и сравнивать k с нулём/единицей.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll euler_phi(ll n) {
    ll result = n;
    for (ll p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            result -= result / p;
        }
    }
    if (n > 1) result -= result / n;
    return result;
}

ll power(ll base, ll exp, ll mod) {
    if (mod == 1) return 0;
    ll result = 1; base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod; exp >>= 1;
    }
    return result;
}

// Цепочка модулей для лестницы: m, phi(m), phi(phi(m)), ..., 1
vector<ll> build_chain(ll m) {
    vector<ll> chain = {m};
    while (m != 1) { m = euler_phi(m); chain.push_back(m); }
    return chain;
}

// b mod m, b задана строкой
ll string_mod(const string& b, ll m) {
    if (m == 1) return 0;
    ll r = 0;
    for (char c : b) r = (r * 10 + (c - '0')) % m;
    return r;
}

// b >= val? b задана строкой
bool string_ge(const string& b, ll val) {
    if ((ll)b.size() > 18) return true;
    ll bval = 0;
    for (char c : b) bval = bval * 10 + (c - '0');
    return bval >= val;
}

// k-- для строки (уменьшение на 1)
string string_decrement(const string& s) {
    string r = s;
    int i = r.size() - 1;
    while (r[i] == '0') { r[i] = '9'; --i; }
    --r[i];
    // убираем ведущие нули
    int start = 0;
    while (start < (int)r.size()-1 && r[start] == '0') ++start;
    return r.substr(start);
}

// Вычисляет a^{a^{a^{...}}} (k копий a) mod chain[depth]
// chain — предвычисленная цепочка модулей
// Возвращает (результат mod chain[depth], флаг "значение >= log2(chain[depth-1])")
// depth — индекс в цепочке (0 = исходный модуль)
pair<ll, bool> solve(ll a, const string& k, const vector<ll>& chain, int depth) {
    ll mod = chain[depth];

    if (mod == 1) return {0, true};

    // k == 0?
    if (k == "0") return {1 % mod, false};

    // k == 1?
    if (k == "1") {
        ll val = a % mod;
        return {val, a >= 64};  // 64 > log2(10^18)
    }

    // Рекурсия: вычисляем показатель mod chain[depth+1] = phi(mod)
    string k_minus_1 = string_decrement(k);
    auto [exp_mod_phi, exp_large] = solve(a, k_minus_1, chain, depth + 1);

    // Применяем обобщённую теорему Эйлера
    ll g = __gcd(a % mod, mod);
    ll phi_mod = chain[depth + 1];  // phi(mod)
    ll exp;

    if (g == 1) {
        exp = exp_mod_phi % phi_mod;
    } else if (exp_large) {
        // exp >= log2(mod), применяем обобщённую формулу
        exp = phi_mod + exp_mod_phi % phi_mod;
    } else {
        // exp маленький — вычисляем напрямую (рекурсия вернула реальное значение)
        exp = exp_mod_phi;
    }

    ll result = power(a, exp, mod);
    return {result, true};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll a; string k;
    cin >> a >> k;

    const ll MOD = 1'000'000'007LL;

    // Строим цепочку: MOD, phi(MOD), phi(phi(MOD)), ...
    // phi(10^9+7) = 10^9+6 = 2 * 500000003
    // phi(10^9+6) = phi(2)*phi(500000003) = ...
    // Цепочка конечна: достигает 1 за O(log MOD) = ~30 шагов
    vector<ll> chain = build_chain(MOD);

    auto [result, _] = solve(a, k, chain, 0);
    cout << result << "\n";
    return 0;
}

Сложность:

• Глубина рекурсии: O(log MOD) ≈ 30.
• На каждом уровне: O(|k| + √chain[depth]) для string_decrement и euler_phi.
• Итого: O(|k| · log MOD + log²MOD · log MOD) = O(|k| · log n + log³ n).

Почему цепочка конечна и короткая?

• MOD = 10^9 + 7 (простое), φ(MOD) = 10^9 + 6
• φ(10^9 + 6) = φ(2 · 500000003) = φ(2) · φ(500000003) = 1 · 500000002 = 500000002
• φ(500000002) = ... и т.д.

Ключевой факт: для n > 2 всегда φ(n) ≤ n/2 (поскольку φ(n) ≤ n−1 и φ(n) чётно для n > 2). Поэтому цепочка убывает как минимум вдвое каждые два шага.

Задачи для самостоятельного решения

Типичные ошибки

1. Забытый базовый случай φ(1) = 1.

// В решете phi[1] должно быть 1, не 0
// Инициализация iota начинает с phi[0]=0, phi[1]=1 — правильно

2. Неправильное применение теоремы Эйлера при gcd(a,n) > 1.

// Неверно при gcd(a,n) > 1:
ll exp = b % euler_phi(n);  // a^{b mod phi(n)} != a^b (mod n)
// Верно:
ll exp = euler_phi(n) + b % euler_phi(n);  // при b >= log2(n)

3. Порядок факторов в решете.

// Неверно — phi[j] /= i может стать нецелым:
phi[j] = phi[j] * (i-1) / i;  // деление может потерять точность
// Верно — сначала вычитаем:
phi[j] -= phi[j] / i;  // phi[j] *= (1 - 1/i), делится нацело

4. Применение формулы к n = 0 или n = 1. φ(0) не определено. φ(1) = 1, не 0. Проверяйте граничные случаи.

5. Переполнение в решете при большом N.

// При N = 10^7 и phi хранится в int: 10^7 * 10^7 = 10^14 — переполнение при умножении
// Решение: phi хранится в long long, или вычисляется через вычитание, не умножение
phi[j] -= phi[j] / i;  // это безопасно: phi[j]/i <= phi[j] <= j <= N

6. Неверная длина цепочки для лестницы Эйлера. Цепочка φ обязательно достигает 1. Но если вы предполагаете фиксированную длину (например, 100), это может быть слишком много или мало. Строите динамически до условия chain.back() == 1.

7. Игнорирование случая a = 1 в лестнице. 1^{всё_что_угодно} = 1. При a = 1 ответ всегда 1, независимо от k и m.

Совет профессионала

На Codeforces часто встречаются задачи вида «найти x такое, что a^x ≡ b (mod m)». Стандартный BSGS (глава 4) находит дискретный логарифм, но если нужно «итерированно» применять φ к показателю — это уже лестница Эйлера. Различайте два класса задач.

Второй совет: для задач на суммирование φ(1) + φ(2) + … + φ(n) при n до 10^11 используйте метод Мин-25 (Min-25 sieve) — он работает за O(n^{2/3} / log n) и является эталонным подходом на соревнованиях уровня Codeforces Div.1 E.

Третий практический момент: тождество ∑_{d|n} φ(d) = n — отличный инструмент отладки. Если ваша реализация φ даёт неверную сумму по делителям, ищите баг именно там.

Итог

Функция Эйлера φ(n) — элегантное обобщение понятия взаимной простоты. Её мультипликативность, доказанная через изоморфизм колец, позволяет вычислять φ через факторизацию за O(√n) или для всех чисел до N за O(N) (линейное решето) или O(N log log N) (решето Эратосфена).

Центральное теоретическое тождество ∑_{d|n} φ(d) = n связывает функцию Эйлера со всеми делителями числа и является полезным инструментом отладки.

Практически важнейшее применение — редукция больших показателей степеней: при gcd(a,n)=1 можно заменить b на b mod φ(n). Обобщённая теорема Эйлера распространяет это и на случай gcd(a,n)>1.

«Лестница Эйлера» превращает задачу о башенных степенях (a^{a^{a^{…}}}) в рекурсивную задачу глубиной O(log n), что делает решение эффективным.