Число и сумма делителей через факторизацию: формулы и реализация
Знаю, что можно найти количество делителей числа, перебирая до корня. Но если число задано разложением n = p1^a1 · p2^a2 · ..., есть же формулы для количества и суммы делителей напрямую? Как они выводятся и как аккуратно посчитать по модулю?
2 ответа
Да, через факторизацию обе величины считаются мгновенно.
Количество делителей d(n) = (a1+1)·(a2+1)·...·(ak+1). Идея: любой делитель — это выбор степени каждого простого от 0 до ai, то есть (ai+1) вариантов независимо для каждого простого, перемножаем.
Сумма делителей σ(n) = ∏ (p_i^{a_i+1} − 1) / (p_i − 1). Это произведение геометрических прогрессий 1 + p + p^2 + ... + p^{a} для каждого простого — раскрыв скобки, получишь ровно сумму всех делителей.
long long count_divisors(long long n) {
long long d = 1;
for (long long p = 2; p * p <= n; p++)
if (n % p == 0) {
int a = 0;
while (n % p == 0) { n /= p; a++; }
d *= (a + 1);
}
if (n > 1) d *= 2; // оставшийся простой в степени 1
return d;
}
long long sum_divisors(long long n) {
long long s = 1;
for (long long p = 2; p * p <= n; p++)
if (n % p == 0) {
long long term = 1, pk = 1;
while (n % p == 0) { n /= p; pk *= p; term += pk; }
s *= term; // 1 + p + ... + p^a
}
if (n > 1) s *= (1 + n);
return s;
}
Сложность — O(sqrt n) на факторизацию. По модулю сумму делителей считай не формулой с делением, а накапливая 1 + p + p^2 + ... напрямую (как в коде term/pk), чтобы не возиться с обратным элементом для (p-1).
Если нужно посчитать d(i) или σ(i) сразу для всех i от 1 до n (а не для одного числа) — не факторизуй каждое отдельно. Используй «решето делителей»: для каждого d прибавляй вклад во все кратные.
// число делителей для всех i = 1..n за O(n log n)
vector<int> d(n+1, 0);
for (int dd = 1; dd <= n; dd++)
for (int j = dd; j <= n; j += dd)
d[j]++;
Это O(n log n) суммарно (гармонический ряд). Аналогично для суммы делителей — прибавляй dd вместо 1. На олимпиаде это частый паттерн, когда нужна мультипликативная функция на всём отрезке.