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

Представьте задачу: найти x mod 10^18 такое, что x³ + 2x = 5. Как начать? Можно попробовать x ≡ 5 (mod 10) — это выполнено при x ≡ 5 (mod 10). Затем уточнить: x ≡ 15 (mod 100)? Нет, 15³ + 30 = 3375 + 30 = 3405 ≡ 05 (mod 100) — не то. Методично уточняем решение от mod p к mod p², p³ и так далее.

Это и есть суть p-адических чисел — систематического метода подъёма решений уравнений от mod p до mod p^k, известного как лемма Хензеля.

В соревновательном программировании p-адические идеи появляются в:

• Задачах "найти x mod p^k, удовлетворяющий уравнению f(x) ≡ 0 (mod p^k)"
• Нахождении последней ненулевой цифры n! или C(n,k)
• Вычислении точного значения p-адической валюации
• Задачах о NTT с большими модулями (вида p^k)
• Задачах с делимостью на высокие степени простых

---

Теория

p-адическая норма и валюация

Зафиксируем простое число p. Для любого ненулевого целого числа n определим p-адическую валюацию v_p(n) как наибольшую степень p, делящую n:

v_p(n) = max{k ∈ Z≥0 : p^k | n}

Например: v_2(12) = 2 (12 = 4·3), v_3(12) = 1, v_5(12) = 0.

Расширяем на рациональные числа: v_p(a/b) = v_p(a) − v_p(b).

Свойства валюации:

• v_p(xy) = v_p(x) + v_p(y)
• v_p(x + y) ≥ min(v_p(x), v_p(y)) (ультраметрическое неравенство)
• v_p(x + y) = min(v_p(x), v_p(y)) если v_p(x) ≠ v_p(y)
• v_p(0) = +∞ (по соглашению)

p-адическая норма: |x|_p = p^{−v_p(x)} (при x ≠ 0), |0|_p = 0.

Эта норма задаёт ультраметрику: d_p(x, y) = |x − y|_p. В этой метрике числа "близки", если их разность делится на высокую степень p. Пример: в 5-адической метрике числа 1 и 126 = 1 + 5³ очень близки: |126 − 1|_5 = |125|_5 = 5^{−3}.

p-адические целые числа Z_p

Внимание: Z_p (p-адические целые) — не то же самое, что Z/pZ (вычеты по модулю p)! Это разные объекты.

Определение Z_p. p-адическое целое число — формальный степенной ряд:

x = a₀ + a₁p + a₂p² + a₃p³ + ..., где aᵢ ∈ {0, 1, ..., p−1}

Это похоже на запись числа в p-ичной системе счисления, но без ограничения на число цифр — ряд бесконечный вправо.

Конструктивное определение. Z_p — это проективный предел:

Z_p = lim← Z/p^k Z = {(x₁, x₂, x₃, ...) : xₖ ∈ Z/p^k Z, xₖ ≡ x_{k-1} (mod p^{k-1})}

Говоря проще: p-адическое число — это бесконечная последовательность совместных вычетов: x mod p, x mod p², x mod p³, ...

Обычные целые числа вложены в Z_p: n ∈ Z соответствует ряду с конечными цифрами (с ведущими нулями).

Отрицательные числа в Z_p. Как записать −1? Это p-1 + (p−1)·p + (p−1)·p² + ... (аналог "...999" в десятичной). Проверка: (p−1)(1 + p + p² + ...) = (p−1)·1/(1−p) = −1 формально. В Z_p это сходится!

Кольцо Z_p. Операции сложения и умножения на Z_p определяются естественно как пределы операций на Z/p^kZ. Z_p — это область целостности, и поле дробей Z_p — это поле p-адических чисел Q_p.

p-адическое разложение числа

Любое целое n ≥ 0 записывается в p-ичной системе. Это его p-адическое разложение (конечное). Для n < 0 разложение бесконечное: −n = p^∞ − n (аналог дополнения до p^∞).

Алгоритм нахождения p-адического разложения n (mod p^k):

digits[0] = n mod p;  n = n / p;
digits[1] = n mod p;  n = n / p;
...
digits[k-1] = n mod p;

Это просто запись n в p-ичной системе, обрезанная до k цифр.

Лемма Хензеля

Теорема (Лемма Хензеля). Пусть f(x) ∈ Z[x] — многочлен с целыми коэффициентами, p — простое. Если:

1. f(x₀) ≡ 0 (mod p)
2. f'(x₀) ≢ 0 (mod p)

То существует единственный x₁ ∈ Z/p²Z такой, что x₁ ≡ x₀ (mod p) и f(x₁) ≡ 0 (mod p²). Более того, существует единственное p-адическое целое x ∈ Z_p с f(x) = 0 и x ≡ x₀ (mod p).

Доказательство (конструктивное). По индукции. Предположим, f(xₖ) ≡ 0 (mod p^k). Ищем xₖ₊₁ = xₖ + tₖ · p^k при tₖ ∈ {0, ..., p−1}. По формуле Тейлора:

f(xₖ + tₖp^k) = f(xₖ) + f'(xₖ) · tₖp^k + O(p^{2k})

При k ≥ 1 член O(p^{2k}) кратен p^{k+1}. Нам нужно:

f(xₖ) + f'(xₖ) · tₖp^k ≡ 0 (mod p^{k+1})

Разделим на p^k:

f(xₖ)/p^k + f'(xₖ) · tₖ ≡ 0 (mod p)

(Так как f(xₖ) ≡ 0 (mod p^k), деление корректно.)

Поскольку f'(x₀) ≢ 0 (mod p) и xₖ ≡ x₀ (mod p), имеем f'(xₖ) ≢ 0 (mod p). Значит, tₖ однозначно определён:

tₖ = −(f(xₖ)/p^k) · (f'(xₖ))⁻¹  (mod p)

Итерируя, получаем единственное решение x в Z_p. □

Скорость сходимости. Если f(xₖ) ≡ 0 (mod p^k), то после одной итерации Ньютона f(xₖ₊₁) ≡ 0 (mod p^{2k}) — квадратичная сходимость! Для получения решения mod p^{64} достаточно 7 итераций.

Обобщённая лемма Хензеля. Если f'(x₀) ≡ 0 (mod p), но f(x₀) ≡ 0 (mod p^{2k+1}) для некоторого k ≥ v_p(f'(x₀)), то подъём всё равно возможен (но решений может быть несколько или ноль).

Применения в CP

Задача типа 1: найти x (0 ≤ x < p^k), удовлетворяющий полиномиальному сравнению f(x) ≡ 0 (mod p^k).

Алгоритм: найти корень x₀ mod p (перебор), затем k−1 раз применить лемму Хензеля.

Задача типа 2: вычислить v_p(f(n)) для некоторой функции f.

Пример: v_p(n!) по формуле Лежандра (глава 23).

Задача типа 3: вычислить последнюю ненулевую цифру n! по модулю p^k.

Использует p-адическое разложение n и рекурсивное вычисление через формулу Адамара–Вильсона.

---

Ключевые формулы

---

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

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

// ==================== Базовые операции ====================

ll powmod(ll a, ll b, ll m) {
    ll res = 1; a %= m;
    while (b > 0) {
        if (b & 1) res = (lll)res * a % m;
        a = (lll)a * a % m;
        b >>= 1;
    }
    return res;
}

// Обратный элемент mod m (расширенный Евклид)
ll modinv(ll a, ll m) {
    ll g = m, x = 0, y = 1;
    if (a == 0) return 0; // нет обратного
    ll ta = a;
    while (ta != 0) {
        ll q = g / ta;
        g -= q * ta; swap(g, ta);
        x -= q * y; swap(x, y);
    }
    if (g != 1) return -1; // не существует
    return (x % m + m) % m;
}

// ==================== Лемма Хензеля ====================

// Один шаг подъёма: xₖ → xₖ₊₁
// Вход: x₀ - корень f mod p^k,
//        p, k - простое и текущая степень,
//        f, df - функция и производная
// Выход: корень mod p^{2k} (квадратичный подъём)
// или -1, если подъём невозможен
ll hensel_step(ll x0, ll p, ll pk, // pk = p^k
               auto f, auto df) {
    ll fx = f(x0, pk * pk);   // f(x₀) mod p^{2k}
    ll dfx = df(x0, p);       // f'(x₀) mod p
    ll inv_df = modinv(((dfx % p) + p) % p, p);
    if (inv_df == -1) return -1; // не можем поднять
    // tₖ = -(f(xₖ)/p^k) / f'(xₖ) mod p
    ll pk_val = pk; // p^k
    if (fx % pk_val != 0) return -1; // f(x₀) не кратно p^k — ошибка
    ll coeff = (fx / pk_val % p + p) % p;
    ll t = (p - (lll)coeff * inv_df % p) % p;
    return x0 + t * pk_val;
}

// Полный подъём: найти x mod p^k, удовлетворяющий f(x) ≡ 0 (mod p^k)
// Возвращает все решения
vector<ll> hensel_lift(ll p, int k, auto f, auto df) {
    // Шаг 1: найти корни mod p
    vector<ll> roots_p;
    for (ll x = 0; x < p; x++) {
        if (f(x, p) == 0) roots_p.push_back(x);
    }
    // Шаг 2: поднять каждый корень
    vector<ll> current = roots_p;
    ll pk = p; // текущее p^k
    for (int step = 1; step < k; step++) {
        vector<ll> next;
        for (ll x : current) {
            ll fx = f(x, pk * p);
            if (fx % pk != 0) continue; // не корень на этом уровне — skip
            ll dfx = ((df(x, p) % p) + p) % p;
            if (dfx != 0) {
                // Единственное продолжение
                ll inv_df = modinv(dfx, p);
                ll t = (p - (fx / pk % p + p) % p * inv_df % p) % p;
                next.push_back(x + t * pk);
            } else {
                // f'(x₀) ≡ 0 (mod p): нет продолжения или p продолжений
                if (fx % (pk * p) == 0) {
                    // p продолжений
                    for (ll t = 0; t < p; t++)
                        next.push_back(x + t * pk);
                }
                // Иначе 0 продолжений
            }
        }
        current = next;
        pk *= p;
    }
    return current;
}

// ==================== Пример: решение x² ≡ a (mod p^k) ====================

// Квадратный корень по модулю p^k (p нечётное)
// Используем Хензель с f(x) = x² - a
ll sqrt_mod_pk(ll a, ll p, int k) {
    // Базовый корень mod p (алгоритм Тонелли-Шэнкса)
    if (a % p == 0) {
        // Особый случай: a кратно p
        return 0; // упрощение
    }
    // Тонелли-Шэнкс для корня mod p
    auto tonelli_shanks = [&](ll n, ll p) -> ll {
        if (p == 2) return n & 1;
        if (powmod(n, (p-1)/2, p) != 1) return -1; // нет корня
        if (p % 4 == 3) return powmod(n, (p+1)/4, p);
        // Общий случай Тонелли-Шэнкса
        ll q = p - 1, s = 0;
        while (q % 2 == 0) { q /= 2; s++; }
        ll z = 2;
        while (powmod(z, (p-1)/2, p) != p-1) z++;
        ll m = s, c = powmod(z, q, p), t = powmod(n, q, p), r = powmod(n, (q+1)/2, p);
        while (true) {
            if (t == 1) return r;
            ll i = 1; ll tmp = (lll)t * t % p;
            while (tmp != 1) { tmp = (lll)tmp * tmp % p; i++; }
            ll b = powmod(c, 1LL << (m - i - 1), p);
            m = i;
            c = (lll)b * b % p;
            t = (lll)t * c % p;
            r = (lll)r * b % p;
        }
    };

    ll x = tonelli_shanks(a % p, p);
    if (x == -1) return -1; // нет корня mod p

    // Поднимаем по Хензелю
    ll pk = p;
    for (int step = 1; step < k; step++) {
        // f(x) = x² - a
        ll fx = ((lll)x * x - a) % (pk * p);
        if (fx < 0) fx += pk * p;
        ll dfx = 2 * x % p;
        if (dfx < 0) dfx += p;
        ll inv_df = modinv(dfx, p);
        ll t = (p - (lll)(fx / pk % p) * inv_df % p) % p;
        x = x + t * pk;
        pk *= p;
    }
    return x % pk;
}

// ==================== p-адическая валюация и применения ====================

// Ввод: n - число, p - простое
// Вывод: v_p(n)
int valuation(ll n, ll p) {
    if (n == 0) return INT_MAX; // по соглашению +∞
    int v = 0;
    while (n % p == 0) { n /= p; v++; }
    return v;
}

// v_p(n!) — формула Лежандра (глава 23, но нужна здесь)
ll legendre_formula(ll n, ll p) {
    ll result = 0;
    ll pk = p;
    while (pk <= n) {
        result += n / pk;
        if (pk > n / p) break; // предотвращение переполнения
        pk *= p;
    }
    return result;
}

// ==================== Пример: поднятие для NTT ====================

// Задача: выполнить NTT по модулю M = p^k
// где p = 998244353 (простое с корнем из 1 высокого порядка)
// Техника: вычислить NTT mod p, затем поднять по Хензелю до mod p^k
// (детали требуют аккуратной реализации, набросок ниже)

// Символ Лежандра (нужен для Хензеля)
int legendre_symbol(ll a, ll p) {
    ll r = powmod(a % p, (p-1)/2, p);
    if (r == p-1) return -1;
    return (int)r;
}

// ==================== p-адический логарифм и экспонента ====================
// Для u ≡ 1 (mod p): log_p(u) = (u-1) - (u-1)²/2 + (u-1)³/3 - ...
// Сходится в Z_p при v_p(u-1) ≥ 1 (для p нечётного)
// Практически: вычисляем до нужной точности

ll p_adic_log(ll u, ll p, int k) {
    // Вычисляем log_p(u) mod p^k
    // u ≡ 1 (mod p) — предусловие
    ll pk = 1;
    for (int i = 0; i < k; i++) pk *= p;
    ll result = 0;
    ll upow = (u - 1 + pk) % pk; // u - 1
    ll upow_i = upow;
    for (int i = 1; i <= k * 64; i++) { // достаточно много слагаемых
        if (upow_i == 0) break;
        ll term = upow_i * modinv(i, pk) % pk;
        if (i % 2 == 1) result = (result + term) % pk;
        else result = (result - term + pk) % pk;
        upow_i = (lll)upow_i * upow % pk;
    }
    return result;
}

int main() {
    // Пример: sqrt(-1) mod 5^4 = 625
    // Знаем: 2² = 4 ≡ -1 (mod 5), значит x₀ = 2
    ll x = sqrt_mod_pk(624, 5, 4); // ищем x² ≡ -1 ≡ 624 (mod 625)
    cout << "x² ≡ -1 (mod 625): x = " << x << "\n";
    cout << "Проверка: " << (lll)x * x % 625 << " (должно быть 624)\n";

    // Формула Лежандра
    cout << "v_2(100!) = " << legendre_formula(100, 2) << "\n"; // 97

    return 0;
}

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

• hensel_lift: O(p + k) — перебор корней mod p + k шагов подъёма, каждый O(log p).
• sqrt_mod_pk: O(log² p + k log p) — Тонелли-Шэнкс + k шагов Хензеля.
• legendre_formula: O(log_p n).

---

Разбор задачи 1 (средняя)

Задача. Дано простое p и числа a, k. Найти все x ∈ [0, p^k) такие, что x³ ≡ a (mod p^k). Гарантируется, что решение существует. p ≤ 10^9, k ≤ 18, p^k представимо в int64.

Решение. Используем hensel_lift с f(x) = x³ − a, f'(x) = 3x².

// f(x) mod m
auto f = [&](ll x, ll m) -> ll {
    return ((lll)x % m * ((lll)x * x % m) % m - a % m + m) % m;
};
// f'(x) mod m
auto df = [&](ll x, ll m) -> ll {
    return (3LL * x % m * x % m) % m;
};

vector<ll> solutions = hensel_lift(p, k, f, df);
for (ll x : solutions)
    cout << x << "\n";

Число решений. При gcd(3, p−1) = 1 (т.е. p ≢ 1 mod 3) — ровно одно решение. При p ≡ 1 (mod 3) — одно или три (зависит от a).

Сложность: O(p + k log p) — линейный проход по [0,p) для базовых корней + k шагов Хензеля.

---

Разбор задачи 2 (сложная)

Задача. Дано n. Найти последнюю цифру числа n! (в десятичной). А точнее, найти последнюю ненулевую цифру n!.

Решение. n! имеет v_5(n!) нулей в конце (по формуле Лежандра). Нам нужна цифра на позиции v_5(n!) справа.

Это эквивалентно вычислению n!/5^{v_5(n!)} · 2^{...} · ... mod 10. Используем следующий факт:

Лемма. Пусть n! = 2^a · 5^b · m, где gcd(m, 10) = 1. Тогда последняя ненулевая цифра = (m · 2^{a−b}) mod 10.

Вычисление m mod 10 через p-адический подход:

// Последняя ненулевая цифра n!
// Алгоритм: Wilson's theorem + рекурсия
// n! / (5^e5 * 2^e2) mod 10 = (n!/5^e5 mod 5) * (inv(2^e2) mod 5) * ...
// Детали:
// Определим f(n) = ∏{k=1}^{n} k, где p ∤ k (mod p^k)
// По формуле Вильсона: f(p-1) ≡ -1 (mod p)
// f(n) ≡ (-1)^{floor(n/p)} * f(n mod p) (mod p) — ключевое рекуррентное соотношение

int last_nonzero_digit_factorial(long long n) {
    // Упрощённая версия для последней цифры в десятичной
    // Используем формулу для v_2(n!) и v_5(n!)
    long long e5 = legendre_formula(n, 5);
    long long e2 = legendre_formula(n, 2);
    // n! / (2^e2 * 5^e5) mod 2 и mod 5, затем CRT
    // Для реального решения нужна рекурсия по Холловей/Фишер
    // (детальная реализация выходит за рамки, даём набросок)
    return -1; // placeholder
}

Полная реализация использует следующую рекуррентность (формула Арнота):

• Определим g(n) = ∏_{1≤k≤n, 5∤k} k (mod 5). Тогда g(5m+r) = g(4)^m · g(r) (mod 5), где g(4) = 24 ≡ 4 (mod 5).
• n! = 5^{n/5} · (n/5)! · g(n) (mod 5, с корректировкой знаков).

---

Разбор задачи 3 (ICPC WF / CF Div.1 E)

Задача (CF 1514F, адаптация). Даны n, m, p (простое). Найти ∑{i=0}^{n} ∑{j=0}^{m} C(i+j, i) mod p^2, при n, m ≤ 10^9.

Почему нужна p-адика? Сама сумма не делится на p, но внутри много слагаемых делятся на p. Нужно работать точно по модулю p².

Решение через обобщённые коэффициенты Лукаса.

Теорема Лукаса работает только mod p. Для mod p^k нужна теорема Гранвилля. Ключевая идея: C(n, k) mod p^a — это произведение (с учётом переноса) цифр в p-ичной записи n.

Конкретная формула: обозначим n = ∑ nᵢpⁱ — цифры в p-ичной записи. Тогда:

C(n, k) / p^{v_p(C(n,k))} ≡ (-1)^{v_p(C(n,k))} · ∏ C(nᵢ, kᵢ)  (mod p)

(теорема Кравчука-Гранвилля). Для модуля p² нужна более тонкая версия.

// v_p(C(n, k)) — через теорему Куммера (глава 23)
// = число переносов при сложении k и n-k в p-ичной записи

ll kummer_carry(ll n, ll k, ll p) {
    ll carries = 0;
    ll carry = 0;
    ll a = k, b = n - k;
    while (a > 0 || b > 0) {
        ll sum = a % p + b % p + carry;
        carry = sum / p;
        carries += carry;
        a /= p; b /= p;
    }
    return carries;
}

// C(n, k) mod p^2 через формулу Эндрю Гранвилля
// (детальная реализация многострочная, приводим ключевую идею)
// C(n, k) = n! / (k! * (n-k)!)
// Вычисляем v_p(n!), v_p(k!), v_p((n-k)!) через Лежандра
// Разность = v_p(C(n,k)) = количество переносов (теорема Куммера)
// Вычисляем "отношение" n! / (k! * (n-k)!) mod p^2 через
// p-адический логарифм факториала

ll binomial_mod_p2(ll n, ll k, ll p) {
    if (k < 0 || k > n) return 0;
    ll p2 = p * p;
    // Степень p в C(n,k)
    ll e = kummer_carry(n, k, p);
    if (e >= 2) return 0; // кратно p² -> 0 mod p²
    // Вычисляем числитель и знаменатель mod p^{2+e}
    // Используем Wilson + рекуррентность
    // (упрощённо для e=0)
    // ... (полная реализация требует формулы Адамара-Вильсона)
    return -1; // placeholder
}

Полное решение CF 1514F требует формулы Эндрю Гранвилля и аккуратной реализации факториала в Z_p. Это одна из самых технически сложных тем в CP.

---

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

---

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

1. Путаница Z_p и Z/pZ. Z_p (p-адические целые) содержат Z/pZ как фактор, но сами по себе бесконечны. В программировании мы работаем с конечными приближениями Z/p^kZ.
2. Забыть проверить условие f'(x₀) ≢ 0 (mod p). При f'(x₀) ≡ 0 алгоритм другой: нужно проверить делимость f(x₀) на p^{2v+1} (где v = v_p(f'(x₀))), и может быть 0 или p продолжений.
3. Переполнение при умножении. При работе mod p^k для k = 9 и p = 10, p^k = 10^9 — умножение двух таких чисел требует __int128.
4. Неверная формула шага Хензеля. Правильная формула: x_{k+1} = x_k − f(x_k) / f'(x_k), где деление в Z_p (обратный по модулю p^k). Ошибка: брать обратный к f'(x_k) по модулю p^k вместо p.
5. Игнорировать случай e = v_p(f(x₀)) > 0 до начала подъёма. Если f(x₀) ≡ 0 (mod p) но не mod p², первый шаг Хензеля всё равно валиден при f'(x₀) ≢ 0 (mod p).

---

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

Лемма Хензеля — это "теорема Ньютона-Рафсона для p-адических чисел". Интуиция: мы ищем корень в ультраметрическом пространстве, где метод Ньютона сходится квадратично. Ключевой инсайт: если f(x₀) ≡ 0 (mod p) и f'(x₀) ≢ 0 (mod p), то решение существует и единственно в Z_p — никакого анализа на каждом шаге не нужно, просто итерируем формулу.

На соревнованиях p-адика чаще всего нужна неявно: задача звучит как "найти x mod M", а M = p^k. Сигнал: если в задаче фигурирует "найти x mod 10^9" с нелинейным уравнением, скорее всего нужна Хензель с p = 2 и p = 5.

---

Итог

p-адические числа предоставляют систематический способ работать с уравнениями по модулям высоких степеней простых. Лемма Хензеля — главный инструмент: если f(x₀) ≡ 0 (mod p) и f'(x₀) ≢ 0 (mod p), решение единственным образом поднимается до Z_p. Квадратичная сходимость (k шагов дают точность p^{2^k}) делает алгоритм исключительно эффективным. На практике в CP p-адика нужна для задач о вычетах по высоким степеням простых, последних цифрах факториалов, и биномиальных коэффициентах mod p^k.