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

Соревновательное программирование требует владения рядом специфических числовых инструментов, которые регулярно появляются в задачах, но не укладываются в одну большую тему. Эта глава охватывает несколько таких техник:

1. Числа Прота и тест Прота — специальный тест простоты для чисел вида k·2^n + 1
2. Числа Мерсенна и тест Лукаса-Лемера — проверка простоты 2^p − 1
3. Формула Лежандра: точная степень вхождения простого p в n!
4. Теорема Куммера: степень p в биномиальном коэффициенте C(n+m, n) через переносы

Объединяет их тема p-адической валюации — измерения того, "насколько сильно" простое p делит данное число.

---

Теория

Числа Прота и тест Прота

Определение. Число Прота — число вида N = k · 2^n + 1, где k нечётно и k < 2^n.

Примеры: 3 = 1·2+1, 5 = 1·4+1, 13 = 3·4+1, 17 = 1·16+1, 41 = 5·8+1.

Теорема Прота (1878). Число Прота N = k·2^n + 1 простое тогда и только тогда, когда существует a такое, что:

a^{(N-1)/2} ≡ -1  (mod N)

Доказательство ("только если" ← простота). Если N простое, то существует примитивный корень g mod N. Тогда a = g^k (mod N) удовлетворяет условию. Точнее: символ Лежандра (a/N) = a^{(N-1)/2} mod N должен быть равен −1, что означает a — квадратный невычет mod N. Поскольку N ≡ 1 (mod 4) (так как 2^n делит N−1, n ≥ 2), то (−1/N) = 1, и тест требует нахождения квадратного невычета a.

Доказательство ("если" → простота). Пусть a^{(N-1)/2} ≡ −1 (mod N). Тогда порядок a mod N делит N−1 = k·2^n, но не делит (N−1)/2 = k·2^{n-1}. Значит, порядок a кратен 2^n. Это означает, что 2^n | φ(q) для каждого простого делителя q числа N. Но q | N = k·2^n + 1, значит q ≡ 1 (mod 2^n) (при условии k < 2^n: N < 2^{2n+1}, q < N, q ≡ 1 (mod 2^n), поэтому q ≥ 2^n + 1 > √N). Тогда N = q (одно простое), т.к. q > √N. □

Алгоритм теста Прота: для данного N = k·2^n + 1 перебираем a = 3, 5, 7, ... до нахождения a с a^{(N-1)/2} ≡ −1 (mod N). В среднем нужно O(1) попыток (плотность квадратных невычетов ≈ 1/2).

Зачем в CP? В задачах на поиск "специальных" больших простых, генерацию простых для NTT (прим.: простые для NTT имеют вид c·2^k + 1 — это числа Прота), а также в криптографических задачах.

// Тест Прота для N = k * 2^n + 1
bool proth_test(long long N) {
    if (N <= 1) return false;
    if (N == 2 || N == 3) return true;
    // Находим k и n: N = k * 2^n + 1
    long long tmp = N - 1;
    int n = 0;
    while (tmp % 2 == 0) { tmp /= 2; n++; }
    long long k = tmp;
    if (k >= (1LL << n)) return false; // не число Прота
    // Перебираем a
    for (long long a = 3; a < N; a += 2) {
        // Вычисляем a^{(N-1)/2} mod N
        long long pow = powmod(a, (N - 1) / 2, N);
        if (pow == N - 1) return true;  // a^{(N-1)/2} ≡ -1 (mod N)
    }
    return false;
}

Числа Мерсенна и тест Лукаса-Лемера

Определение. Число Мерсенна — число вида M_p = 2^p − 1. При составном p: M_p составное (т.к. 2^{ab} − 1 = (2^a − 1)(2^{a(b-1)} + ... + 1)). Поэтому простые числа Мерсенна ищут только при простом p.

Примеры простых Мерсенна: M_2=3, M_3=7, M_5=31, M_7=127, M_13=8191, ..., M_{82589933} (крупнейшее известное простое, 2024).

Теорема (тест Лукаса-Лемера). Для нечётного простого p число M_p = 2^p − 1 простое тогда и только тогда, когда:

s_{p-2} ≡ 0  (mod M_p)

где последовательность s определяется как s_0 = 4 и s_k = s_{k-1}² − 2.

Доказательство (основная идея). Рассмотрим кольцо Z[ω], где ω = (2 + √3)^{1/2}. Последовательность s_k связана с нормами в этом кольце: s_k = ω^{2^k} + ω^{-2^k}. Условие s_{p-2} ≡ 0 (mod M_p) эквивалентно делимости ω^{2^{p-1}} + ω^{-2^{p-1}} на M_p, что через теорию полей Галуа эквивалентно простоте M_p. Подробное доказательство требует теории гауссовых периодов — оно технически нетривиально, но результат красив.

Сложность теста: O(p · M(p)) где M(p) — время умножения p-битных чисел. Современные реализации используют FFT-умножение: O(p² / log p) операций. Для M_{82589933} с ~25 млн цифр это всё ещё занимает несколько часов.

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

// Тест Лукаса-Лемера для малых M_p (p ≤ 63 для long long)
bool lucas_lehmer(int p) {
    if (p == 2) return true;
    // M_p = 2^p - 1
    long long Mp = (1LL << p) - 1;
    // s_0 = 4, s_k = s_{k-1}^2 - 2 (mod M_p)
    __int128 s = 4;
    __int128 mod = Mp;
    for (int i = 0; i < p - 2; i++) {
        s = (s * s - 2) % mod;
        if (s < 0) s += mod;
    }
    return s == 0;
}

// Для больших p нужна библиотека bignum (GMP)
// Но для CP задач p ≤ 60 обычно достаточно

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

• Задачи, где нужно проверить простоту числа вида 2^p − 1
• Генерация простых специального вида для хэшей и NTT
• Задачи на "магические числа" (M_p часто встречаются в задачах на битовые маски)

Формула Лежандра

Теорема (Лежандр, 1808). Степень простого p в факториале n!:

v_p(n!) = ∑_{k=1}^{∞} ⌊n/p^k⌋ = (n − s_p(n)) / (p − 1)

где s_p(n) — сумма цифр числа n в p-ичной системе счисления.

Доказательство первой формулы. Среди чисел 1, 2, ..., n:

• Кратных p ровно ⌊n/p⌋ — каждое вносит одну "лишнюю" p
• Кратных p² ровно ⌊n/p²⌋ — каждое вносит ещё одну p (одну уже посчитали)
• ...

Итого v_p(n!) = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + ...

Доказательство второй формулы. Запишем n в p-ичной системе: n = ∑_i a_i · p^i. Тогда:

n − s_p(n) = ∑_i a_i(p^i − 1) = ∑_i a_i · (p-1) · (1 + p + ... + p^{i-1})

и далее геометрическими рядами получаем то же, что и первая формула. □

Явные следствия:

• v_2(n!) = n − s_2(n) — число нулевых битов ниже старшего
• v_p(n!) ≈ n/(p−1) при больших n
• n! всегда оканчивается на v_5(n!) нулей

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

// Через сумму цифр
long long legendre_digit_sum(long long n, long long p) {
    long long s = 0; // s_p(n)
    long long tmp = n;
    while (tmp > 0) {
        s += tmp % p;
        tmp /= p;
    }
    return (n - s) / (p - 1);
}

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

1. Конец числа: число нулей на конце n! = v_5(n!) = (n − s_5(n)) / 4.
2. Делимость: C(n,k) = n!/(k!(n-k)!) — найти v_p(C(n,k)) = v_p(n!) − v_p(k!) − v_p((n−k)!).
3. Кратность произведения: когда n! делится на p^m?
4. Сравнение с p^k: задачи типа "найти k: p^k | n!" решаются через Лежандра.

Теорема Куммера

Теорема (Куммер, 1852). Степень простого p в биномиальном коэффициенте:

v_p(C(m+n, m)) = число переносов при сложении m и n в p-ичной записи

Доказательство. v_p(C(m+n, m)) = v_p((m+n)!) − v_p(m!) − v_p(n!). По формуле Лежандра (в виде s_p):

v_p(C(m+n, m)) = (m+n−s_p(m+n)) − (m−s_p(m)) − (n−s_p(n)) / (p-1)
               = (s_p(m) + s_p(n) − s_p(m+n)) / (p-1)

При сложении чисел m и n в p-ичной записи каждый перенос уменьшает сумму цифр на p−1 (цифры "поглощаются" в перенос). Если переносов c штук, то s_p(m+n) = s_p(m) + s_p(n) − c(p−1). Поэтому:

v_p(C(m+n, m)) = c = число переносов

Следствие (Теорема Кема). C(n, k) ≢ 0 (mod p) тогда и только тогда, когда каждая цифра k не превышает соответствующую цифру n в p-ичной записи. (Нет переносов = нет кратности p.)

Теорема Лукаса (частный случай при e=1). C(n, k) ≡ ∏_i C(n_i, k_i) (mod p), где n_i, k_i — цифры n, k в p-ичной записи.

// Число переносов при сложении a и b в базе p
long long kummer(long long a, long long b, long long p) {
    long long carries = 0;
    long long carry = 0;
    while (a > 0 || b > 0) {
        long long sum = (a % p) + (b % p) + carry;
        carry = sum / p;
        carries += carry;
        a /= p; b /= p;
    }
    return carries;
}

// v_p(C(n, k)) = v_p(n!) - v_p(k!) - v_p((n-k)!)
long long vp_binom(long long n, long long k, long long p) {
    return legendre(n, p) - legendre(k, p) - legendre(n - k, p);
    // Эквивалентно: kummer(k, n-k, p)
}

// Теорема Лукаса: C(n, k) mod p (p - простое)
long long lucas(long long n, long long k, long long p) {
    if (k > n) return 0;
    if (k == 0) return 1;
    // C(n, k) ≡ C(n mod p, k mod p) * C(n/p, k/p) (mod p)
    return (lucas(n % p, k % p, p) * lucas(n / p, k / p, p)) % p;
}

// C(n, k) mod p через прямую таблицу (для малых p)
long long lucas_direct(long long n, long long k, long long p) {
    if (k > n) return 0;
    long long result = 1;
    while (n > 0) {
        long long ni = n % p, ki = k % p;
        if (ki > ni) return 0;
        // Вычисляем C(ni, ki) mod p
        long long c = 1;
        for (long long i = 0; i < ki; i++) {
            c = c * (ni - i) % p;
            c = c * mod_inverse(i + 1, p) % p; // обратный mod p
        }
        result = result * c % p;
        n /= p; k /= p;
    }
    return result;
}

long long mod_inverse(long long a, long long p) {
    return powmod(a, p - 2, p);
}

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

Применения формулы Лежандра и теоремы Куммера

Задача типа 1. Найти максимальное k такое, что p^k делит C(n, m).

Решение: k = kummer(m, n−m, p) = vp_binom(n, m, p). O(log_p n) время.

Задача типа 2. Является ли C(n, m) нечётным?

Решение: v_2(C(n,m)) = число переносов при сложении m и n−m в двоичной записи = 0 ⟺ нет переносов ⟺ (m AND (n−m)) == 0 ⟺ m OR (n−m) == n ⟺ m AND n == m (каждый бит m есть в n). Это теорема Кема в двоичном виде.

Задача типа 3. Для каждого k найти v_p(C(n, k)) при k = 0, 1, ..., n.

Наивный подход: O(n log n). Лучше: v_p(C(n,k)) = v_p(C(n,k-1)) + (при переходе k-1 → k число переносов меняется на определённую величину). Или: полная таблица через ДП за O(n / (p-1)).

Дополнительно: теорема Сильвестра-Гальяи и p-адические соображения

Наблюдение. Делитель C(p^k, m) при 0 < m < p^k всегда кратен p^{k − v_p(m)} — это следует из Куммера. Более точно: v_p(C(p^k, m)) = k − v_p(m).

Это полезно при доказательстве формальных тождеств и в задачах на полиномиальные коэффициенты.

Центральные биномиальные коэффициенты. C(2n, n) / (n+1) = число Каталана C_n. Степень p в C_n: v_p(C_n) = v_p(C(2n,n)) − v_p(n+1). По Куммеру: v_p(C(2n,n)) = число переносов при сложении n + n в базе p = число позиций, где цифра n ≥ p/2 (т.е. при удвоении происходит перенос).

---

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

---

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

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

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

int vp(ll n, ll p) {
    if (n == 0) return INT_MAX;
    int v = 0;
    while (n % p == 0) { n /= p; v++; }
    return v;
}

// ==================== Формула Лежандра ====================

ll legendre(ll n, ll p) {
    ll res = 0;
    ll pk = p;
    while (pk <= n) {
        res += n / pk;
        if (pk > n / p) break;
        pk *= p;
    }
    return res;
}

// Через сумму цифр в базе p
ll legendre_v2(ll n, ll p) {
    ll s = 0, tmp = n;
    while (tmp) { s += tmp % p; tmp /= p; }
    return (n - s) / (p - 1);
}

// ==================== Теорема Куммера ====================

ll kummer(ll a, ll b, ll p) {
    ll carry = 0, result = 0;
    while (a || b) {
        ll s = a % p + b % p + carry;
        carry = s / p;
        result += carry;
        a /= p; b /= p;
    }
    return result;
}

// v_p(C(n, k))
ll vp_binom(ll n, ll k, ll p) {
    if (k < 0 || k > n) return 0;
    return kummer(k, n - k, p);
}

// ==================== Теорема Лукаса ====================

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;
}

ll modinv(ll a, ll p) { return powmod(a, p - 2, p); }

// C(n, k) mod p для 0 <= k <= n < p (прямое вычисление)
ll C_small(ll n, ll k, ll p) {
    if (k < 0 || k > n) return 0;
    if (k == 0 || k == n) return 1;
    // Вычисляем C(n, k) mod p напрямую (n, k < p)
    // Используем таблицу факториалов
    vector<ll> fact(n + 1);
    fact[0] = 1;
    for (ll i = 1; i <= n; i++) fact[i] = fact[i-1] * i % p;
    vector<ll> inv_fact(n + 1);
    inv_fact[n] = modinv(fact[n], p);
    for (ll i = n - 1; i >= 0; i--) inv_fact[i] = inv_fact[i+1] * (i+1) % p;
    return fact[n] * inv_fact[k] % p * inv_fact[n-k] % p;
}

// Теорема Лукаса: C(n, k) mod p, p - простое
ll lucas(ll n, ll k, ll p) {
    if (k > n) return 0;
    ll result = 1;
    while (n > 0) {
        ll ni = n % p, ki = k % p;
        if (ki > ni) return 0;
        result = result * C_small(ni, ki, p) % p;
        n /= p; k /= p;
    }
    return result;
}

// ==================== Тест Прота ====================

bool proth_test(ll N) {
    if (N < 3) return N >= 2;
    if (N % 2 == 0) return N == 2;
    ll tmp = N - 1;
    int n = 0;
    while (tmp % 2 == 0) { tmp >>= 1; n++; }
    ll k = tmp;
    // Проверяем: k < 2^n
    if (n < 64 && k >= (1LL << n)) return false; // не Прота
    // Перебираем a
    for (ll a = 3; a < N; a += 2) {
        ll r = powmod(a, (N - 1) / 2, N);
        if (r == N - 1) return true;
    }
    return false;
}

// ==================== Тест Лукаса-Лемера ====================

bool lucas_lehmer(int p) {
    if (p == 2) return true;
    if (p % 2 == 0) return false;
    // M_p = 2^p - 1; работает для p <= 62 в long long
    if (p > 62) {
        // Нужна bignum арифметика
        return false; // заглушка
    }
    ll Mp = (1LL << p) - 1;
    __int128 s = 4;
    __int128 mod = Mp;
    for (int i = 0; i < p - 2; i++) {
        s = s * s - 2;
        s %= mod;
        if (s < 0) s += mod;
    }
    return s == 0;
}

// ==================== Число нулей на конце n! ====================

ll trailing_zeros(ll n) {
    return legendre(n, 5);
}

// ==================== Биномиальный коэффициент mod p^k (упрощённо) ====================
// Гранвилль-Лукас для mod p^2
// Использует формулу Вильсона: (p-1)! ≡ -1 (mod p)
// и рекуррентность для факториала mod p^2

// Вычисление факториала "без множителей p": n!_p = ∏_{k≤n, p∤k} k
// По лемме Вильсона: n!_p ≡ (-1)^{⌊n/p⌋} (mod p) для n!_p = ∏_{1≤k≤n, p∤k} k

// ==================== Числа Каталана и их делимость ====================

// v_p(C_n) = v_p(C(2n, n)) - v_p(n+1)
ll catalan_vp(ll n, ll p) {
    return vp_binom(2*n, n, p) - vp(n + 1, p);
}

// C_n mod p (теорема Лукаса для Каталана)
ll catalan_mod_p(ll n, ll p) {
    // C_n = C(2n, n) / (n+1)
    ll num = lucas(2*n, n, p);
    ll den = (n + 1) % p;
    if (den == 0) {
        // Особый случай: p | (n+1), нужен v_p анализ
        // ...
        return 0; // упрощение
    }
    return num * modinv(den, p) % p;
}

// ==================== Полная программа для задачи-примера ====================

// Задача: найти n ≤ 10^18 такое, что v_p(n!) = k
// Бинарный поиск: v_p(n!) монотонно возрастает
ll find_n_with_vp_factorial_eq_k(ll k, ll p) {
    if (k == 0) return 0;
    // v_p(n!) ≥ k ⟺ n ≥ ? (нет точной инверсии)
    // Используем формулу: v_p(n!) ≈ n/(p-1)
    // Бинарный поиск по n
    ll lo = 1, hi = k * (p - 1) + p; // верхняя оценка
    while (lo < hi) {
        ll mid = (lo + hi) / 2;
        if (legendre(mid, p) >= k) hi = mid;
        else lo = mid + 1;
    }
    if (legendre(lo, p) == k) return lo;
    return -1; // нет точного n с v_p(n!) = k (пропущено значение)
}

int main() {
    // Формула Лежандра
    cout << "v_2(100!) = " << legendre(100, 2) << "\n"; // 97
    cout << "v_5(100!) = " << legendre(100, 5) << "\n"; // 24 (нули на конце)

    // Теорема Куммера
    cout << "v_2(C(10,3)) = " << vp_binom(10, 3, 2) << "\n"; // 0 (C(10,3)=120=8*15, v_2=3)
    // Проверка: kummer(3, 7, 2) = переносы при 011+0111=1010 -> один перенос
    // 3 = 011, 7 = 111: 1+1=10 (перенос), 1+1+1=11 (перенос), 0+1=01 -> 2 переноса
    cout << "kummer(3,7,2) = " << kummer(3, 7, 2) << "\n"; // должно быть 3 (v_2(C(10,3))=3)
    // C(10,3) = 120 = 2^3 * 15 → v_2 = 3 ✓

    // Тест Лукаса-Лемера
    vector<int> mersenne_primes = {2, 3, 5, 7, 13, 17, 19, 31};
    for (int p : mersenne_primes) {
        if (lucas_lehmer(p))
            cout << "M_" << p << " = " << ((1LL<<p)-1) << " простое\n";
    }

    // Теорема Лукаса
    cout << "C(10, 4) mod 3 = " << lucas(10, 4, 3) << "\n"; // C(10,4)=210=70*3, ≡ 0
    cout << "C(7, 3) mod 5 = " << lucas(7, 3, 5) << "\n";  // 35 mod 5 = 0

    // Числа Каталана
    cout << "v_2(C_5) = " << catalan_vp(5, 2) << "\n"; // C_5=42=2*21, v_2=1

    return 0;
}

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

• legendre(n, p): O(log_p n) — O(log n / log p) итераций.
• kummer(a, b, p): O(log_p(a+b)) — O(log(max(a,b)) / log p).
• lucas(n, k, p): O(log_p n · p) — рекурсия + C_small.
• proth_test(N): O(sqrt(N) · log N) — O(1) попыток в среднем, каждая O(log N).
• lucas_lehmer(p): O(p) итераций, каждая O(M(p)) — умножение p-битных чисел.

---

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

Задача. Дано n ≤ 10^18. Найти число нулей на конце n!.

Решение. Ответ = v_5(n!) = (n − s_5(n)) / 4 = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + ...

int main() {
    ll n; cin >> n;
    cout << legendre(n, 5) << "\n";
}

Пример. n = 100: 20 + 4 = 24 нуля.

Почему именно 5? Каждая пара множителей 2·5 = 10 даёт одну нулевую цифру. Двоек в n! всегда больше пятёрок (v_2(n!) > v_5(n!) при n > 2), поэтому ограничивающий фактор — пятёрки.

---

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

Задача (CF 620E / аналог). Даны n, k, p (простое). Посчитать ∑_{i=0}^{n} C(n, i) · [v_p(C(n, i)) = k] по модулю 10^9 + 7.

То есть сумма тех биномиальных коэффициентов C(n, i), степень p в которых ровно k.

Решение. По теореме Куммера, v_p(C(n,i)) = число переносов при сложении i + (n−i) в базе p. Но i + (n−i) = n, значит переносы зависят только от цифр i и n в базе p!

Используем цифровое динамическое программирование (digit DP):

Состояние DP: dp[позиция][перенос_накоплен][перенос_идёт] = сумма биномиальных коэффициентов.

Обозначим n = ∑ n_j · p^j. Для каждой позиции j выбираем цифру i_j ∈ [0, p-1]. Перенос при сложении i_j + (n_j − i_j + carry) делает вклад в v_p(C(n, i)).

Точная сумма ∑ C(n, i) = 2^n (все биномиальные коэффициенты). Нам нужна часть с конкретным v_p = k.

// Цифровое ДП для ∑ C(n, i) по i с v_p(C(n,i)) = k
// dp[j][carries] = сумма C(n mod p^j, i mod p^j) по подходящим i
// Переходы: для каждой позиции j выбираем i_j ∈ [0, n_j] (т.к. перенос невозможен)
// (упрощение: без переносов carry=0, i_j ≤ n_j)

// По теореме Кема: v_p(C(n,i)) = 0 ⟺ каждая цифра i_j ≤ n_j
// В общем случае v_p(C(n,i)) = число позиций с "переносом снизу"

// Полная реализация:
ll solve(ll n, int k, ll p, ll mod) {
    // Разбиваем n по цифрам в базе p
    vector<ll> digits;
    ll tmp = n;
    while (tmp > 0) { digits.push_back(tmp % p); tmp /= p; }

    int D = digits.size();
    // dp[carries][carry_in] = (сумма коэф., число цифр обработано)
    // carries = число переносов уже совершённых
    // carry_in = перенос из предыдущей позиции (0 или 1)
    // Значение = сумма ∏ C(n_j, i_j) mod

    // dp[c][cin] = (сумма произведений C(n_j, i_j) для позиций 0..j-1
    //               такая что суммарных переносов было c, и текущий перенос cin)
    vector<vector<ll>> dp(k + 2, vector<ll>(2, 0));
    dp[0][0] = 1;

    for (int j = 0; j < D; j++) {
        ll nj = digits[j];
        vector<vector<ll>> ndp(k + 2, vector<ll>(2, 0));
        for (int c = 0; c <= min(j, k); c++) {
            for (int cin = 0; cin <= 1; cin++) {
                if (!dp[c][cin]) continue;
                // Выбираем i_j ∈ [0, p-1]
                for (ll ij = 0; ij < p; ij++) {
                    ll total = ij + (nj - ij) + cin;
                    // Оп. нет: n_j - i_j может быть < 0
                    // Исправляем: i + (n-i) = n (в одной позиции с учётом переноса)
                    // Правильно: i_j + (n-i)_j + carry_in = nj + carry_in (? нет)
                    // На самом деле: ij + (n mod p^{j+1} / p^j - ij + carry_in) mod p - это сложнее
                    // Опускаем полную реализацию; ключевая идея дана выше
                    (void)total;
                }
            }
        }
        dp = ndp;
    }

    return dp[k][0]; // переносов ровно k, без финального переноса
}

Полная реализация цифрового DP для этой задачи — нетривиальная работа. Ключевая идея: использовать теорему Лукаса для факторизации суммы по позициям (произведение C(n_j, i_j) по позициям).

---

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

Задача (CF 196E / аналог). Дано T ≤ 10^5 запросов. Каждый: дано n, k — найти v_2(C(n, k)).

Решение. Прямое применение теоремы Куммера: v_2(C(n,k)) = kummer(k, n−k, 2) — число переносов при сложении k и n−k в двоичной записи.

// Число переносов при сложении двух чисел в двоичном
// = popcount(k) + popcount(n-k) - popcount(n)  (!)
// Доказательство: s_2(k) + s_2(n-k) = s_2(n) + 2 * carries
// поэтому carries = (popcount(k) + popcount(n-k) - popcount(n)) / 2

ll kummer_2(ll k, ll n) {
    // v_2(C(n, k)) = (popcount(k) + popcount(n-k) - popcount(n)) / 2
    // Но более точно через формулу Лежандра:
    return legendre(n, 2) - legendre(k, 2) - legendre(n - k, 2);
    // Или: (popcount(k) + popcount(n-k) - popcount(n)) - ... нет, Куммер точнее
}

// Оптимальный вариант: O(log n) через формулу со цифрами
ll kummer_fast(ll a, ll b, ll p) {
    // a + b цифры
    ll carry = 0, result = 0;
    while (a || b || carry) {
        ll s = a % p + b % p + carry;
        carry = s / p;
        result += carry;
        a /= p; b /= p;
    }
    return result;
}

// Ещё более быстро для p = 2:
ll kummer_2_fast(ll k, ll n_minus_k) {
    // = (__builtin_popcountll(k) + __builtin_popcountll(n_minus_k)
    //    - __builtin_popcountll(k + n_minus_k)) / ... нет
    // Правильно: (popcount(a) + popcount(b) - popcount(a+b)) - это число переносов в 2-ичном
    // НО: сумма цифр a+b в двоичном = popcount(a)+popcount(b) - 2*carries
    // поэтому carries = (popcount(a) + popcount(b) - popcount(a+b)) / 2 * ... нет!
    // Правильно: popcount(a XOR b) + 2*popcount(a AND b) = popcount(a) + popcount(b)
    // а переносы при сложении: carry_k = (a_k + b_k + carry_{k-1}) >= 2
    // Итог: число переносов = (popcount(a) + popcount(b) - popcount(a+b)) / 1
    //       ... это не так просто
    // Безопасный вариант:
    return kummer_fast(k, n_minus_k, 2);
}

int main() {
    // Тест: v_2(C(10, 3)) = ?
    // C(10, 3) = 120 = 8 * 15 → v_2 = 3
    // Куммер: 3 = 011, 7 = 0111: сложение 011+0111:
    //  1+1=10 (перенос), 1+1+1=11 (перенос), 0+1=01, 0+0+1=01 → 3 переноса? нет
    // 3+7=10=1010. popcount(3)+popcount(7)-popcount(10) = 2+3-2 = 3 → v_2 = 3 ✓
    cout << "v_2(C(10,3)) = " << vp_binom(10, 3, 2) << "\n"; // 3

    // Удобная формула для p=2:
    // v_2(C(n,k)) = (popcount(k) + popcount(n-k) - popcount(n))
    // Так как popcount(a) + popcount(b) - popcount(a+b) = 2 * carries(a,b,2)
    // НО carries(k, n-k) = (popcount(k) + popcount(n-k) - popcount(n)) / ... неверно
    // Правило: carries = (s_2(k) + s_2(n-k) - s_2(n)) / (2-1) = popcount(k)+popcount(n-k)-popcount(n)
    ll n_val = 10, k_val = 3;
    ll alt = __builtin_popcountll(k_val) + __builtin_popcountll(n_val - k_val)
             - __builtin_popcountll(n_val);
    cout << "Через popcount: " << alt << "\n"; // тоже 3 ✓

    // Тест Прота: 41 = 5 * 8 + 1 = 5 * 2^3 + 1, k=5 < 8=2^3 ✓
    cout << "41 простое (тест Прота): " << proth_test(41) << "\n"; // 1

    // Lucas-Lehmer
    cout << "M_7 = 127 простое: " << lucas_lehmer(7) << "\n"; // 1
    cout << "M_11 = 2047 = 23*89 не простое: " << (lucas_lehmer(11) ? "да" : "нет") << "\n"; // нет

    return 0;
}

---

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

---

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

1. Переполнение в формуле Лежандра. При p = 2 и n = 10^18 цикл pk *= p может переполниться. Используйте проверку if (pk > n / p) break; перед умножением.
2. Путаница Куммера и Лукаса. Теорема Куммера даёт v_p(C(n,k)), теорема Лукаса — C(n,k) mod p. Это разные величины!
3. Теорема Кема (Lucas mod p) ≠ Лукас для составного p. Лукас работает только для простых p. Для составного n используйте CRT: разложите n на простые степени и применяйте теорему Гранвилля.
4. Тест Лукаса-Лемера для малых p. M_2 = 3 простое, но последовательность s не применяется при p=2 (специальный случай). M_3 = 7 простое: s_0=4, s_1=14≡0 (mod 7) ✓.
5. Неверный вывод из числа переносов. v_p(C(n,k)) = число переносов при сложении k + (n−k), а НЕ n + k. Аргументы — слагаемые k и n−k, а не n и k.
6. Медленный тест Прота. Перебор a от 2 до N — O(N) попыток. На практике первая удачная a ≤ p/2 при простом N; случайная a с вероятностью 1/2 является квадратным невычетом. Перебор до первого успеха — O(1) ожидаемо.

---

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

Формула Лежандра и теорема Куммера — это "скрытое" p-адическое содержание в стандартных задачах на факториалы и биномиальные коэффициенты. Запомните ключевое тождество:

v_p(C(n, k)) = (s_p(k) + s_p(n-k) - s_p(n)) / (p-1)

где s_p(n) — сумма цифр n в базе p. Для p=2 это (popcount(k) + popcount(n-k) - popcount(n)) — вычисляется за O(1) через встроенную функцию __builtin_popcountll!

Это позволяет решать задачи типа "найти все k ≤ n с v_2(C(n,k)) = 0" за O(2^{количество нулевых бит в n}) через перебор подмасок нулевых битов n (теорема Кема).

Ещё один трюк: v_p(n!) + v_p((p^k - n)!) = k·p^{k-1} − n/(p-1) + O(1) — это позволяет быстро находить v_p в задачах с "дополнением".

---

Итог

Смешанные техники теории чисел объединены темой p-адической валюации. Формула Лежандра v_p(n!) = ∑⌊n/p^k⌋ — быстрый способ подсчитать "вес" простого в факториале. Теорема Куммера связывает v_p(C(n,k)) с числом переносов при сложении k и n−k в p-ичной записи, открывая путь к эффективным алгоритмам через цифровое ДП и bitwise операции. Тест Прота и тест Лукаса-Лемера — специализированные инструменты для проверки простоты чисел особой формы, важные как в теории, так и в практике соревнований.