Divisor Analysis

Complejidad temporal: $\mathcal O(N \log(\max(k_i)))$ .

Cantidad de divisores

Cada divisor del número se puede escribir como $\prod_{i = 1}^N x_i^{\alpha_i}$ donde $0 \leq \alpha_i \leq k_i$ .

Como hay $k_i + 1$ elecciones para $\alpha_i$ , la cantidad de divisores es simplemente $\prod_{i = 1}^N (k_i + 1)$ .

Podemos calcular esto recorriendo los factores primos en tiempo $\mathcal O(N)$ .

Suma de divisores

Sea $S_i$ la suma de divisores considerando solo los primeros $i$ factores primos. La respuesta será $S_N$ .

\begin{aligned} S_i &= S_{i - 1} \sum_{j = 0}^{k_i} x_i^j\\ &= S_{i - 1} \cdot \frac{x_i^{k_i + 1} - 1}{x_i - 1}\\ \end{aligned}

Podemos calcular cada $S_i$ usando exponenciación rápida e inversos modulares en tiempo $\mathcal O(N \log(\max(k_i)))$ .

Producto de divisores

Sean $P_i$ y $C_i$ el producto y la cantidad de divisores considerando solo los primeros $i$ factores primos, respectivamente. La respuesta será $P_N$ .

\begin{aligned} P_i &= P_{i - 1}^{k_i + 1} \left(x_i^{k_i(k_i + 1)/2} \right)^{C_{i - 1}} \end{aligned}

De nuevo, podemos calcular cada $P_i$ usando exponenciación rápida en tiempo $\mathcal O(N \log(\max(k_i)))$ , ¡pero hay un detalle! Puede ser tentador usar $C_{i - 1}$ de los valores calculados previamente en la parte 1 de este problema, pero esos valores van a dar respuestas incorrectas.

Esto es porque $a^b \not \equiv a^{b \bmod p} \pmod{p}$ en general. Sin embargo, por el pequeño teorema de Fermat, $a^b \equiv a^{b \bmod (p - 1)} \pmod{p}$ para $p$ primo, así que podemos guardar $C_i$ módulo $10^9 + 6$ para calcular $P_i$ .

¿Cómo obtenemos esta recurrencia?

Claramente

P_1 = x_1^0x_1^1x_1^2\dots x_1^{k_1} = x_1^\frac{k_1(k_1+1)}{2}

porque todos los $x_i$ son primos. Luego para $P_2$ , tenemos

\begin{aligned} P_2 & = x_1^1\times x_1^2\times x_1^3\times\dots\times x_1^{k_1} \\ & \times x_2 \times x_2x_1 \times x_2x_1^2\times\dots\times x_2x_1^{k_1} \\ & \times x_2^2 \times x_2^2x_1 \times x_2^2x_1^2\times\dots\times x_2^2x_1^{k_1} \\ & \vdots \\ & \times x_2^{k_2} \times x_2^{k_2}x_1 \times x_2^{k_2}x_1^2\times\dots\times x_2^{k_2}x_1^{k_1} \\ & \\ & = P_1 \times P_1x_2^{k_1+1} \times P_1\left(x_2^{k_1+1}\right)^2 \times \dots \times P_1\left(x_2^{k_1+1}\right)^{k_2} \\ & = \prod_{j=0}^{k_2}\left(P_1\left(x_2^{k_1+1}\right)^j\right)\text{.} \end{aligned}

Generalizando a $P_i$ , tenemos

P_i = \prod_{j=0}^{k_i}\left(P_{i-1}\left(x_i^{C_{i-1}}\right)^j\right)\text{.}

La aparición de $C_{i-1}$ en lugar de $k_{i-1} + 1$ se debe a que necesitamos dar a todos los $C_{i-1}$ divisores previos un multiplicador de $x_i^j$ . Simplificando, tenemos

\begin{aligned} P_i & = \prod_{j=0}^{k_i}\left(P_{i-1}\left(x_i^{C_{i-1}}\right)^j\right) \\ & = P_{i-1}^{k_i+1}\prod_{j=0}^{k_i}\left(\left(x_i^{C_{i-1}}\right)^j\right) \\ & = P_{i-1}^{k_i+1}\left(\prod_{j=0}^{k_i}x_i^j\right)^{C_{i-1}} \\ & = P_{i-1}^{k_i+1}\left(x_i^{\sum_{j=0}^{k_i}j}\right)^{C_{i-1}} \\ & = P_{i-1}^{k_i+1}\left(x_i^{k_i(k_i+1)/2}\right)^{C_{i-1}}\text{,} \end{aligned}

que es la recurrencia deseada. Notar que $C_1 = k_1 + 1$ .

C++


#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
const ll MOD = 1e9 + 7;
 
ll expo(ll base, ll pow) {
	ll ans = 1;
	while (pow) {
		if (pow & 1) ans = ans * base % MOD;
		base = base * base % MOD;
		pow >>= 1;
	}
	return ans;
}
 
ll p[100001], k[100001];
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> p[i] >> k[i];
	ll div_cnt = 1, div_sum = 1, div_prod = 1, div_cnt2 = 1;
	for (int i = 0; i < n; i++) {
		div_cnt = div_cnt * (k[i] + 1) % MOD;
		div_sum =
		    div_sum * (expo(p[i], k[i] + 1) - 1) % MOD * expo(p[i] - 1, MOD - 2) % MOD;
		div_prod = expo(div_prod, k[i] + 1) *
		           expo(expo(p[i], (k[i] * (k[i] + 1) / 2)), div_cnt2) % MOD;
		div_cnt2 = div_cnt2 * (k[i] + 1) % (MOD - 1);
	}
	cout << div_cnt << ' ' << div_sum << ' ' << div_prod;
	return 0;
}