Sumdiv

Explicación

Para un entero $A$ , la suma de todos los divisores de $A$ se puede calcular de forma eficiente usando la función de divisores .

La fórmula establece que si $d_1^{p_1} \cdot d_2^{p_2} \cdot ... \cdot d_k^{p_k}$ es la factorización prima de $A$ , entonces la suma de los divisores es:

S = \prod_{i=1}^{k}\frac{d_i^{p_i+1} - 1}{d_i -1}.

En este problema necesitamos calcular la suma de divisores de $A^B$ . Si la factorización prima de $A$ es $d_1^{p_1} \cdot d_2^{p_2} \cdot ... \cdot d_k^{p_k}$ entonces la factorización prima de $A^B$ será $d_1^{B\cdot p_1} \cdot d_2^{B\cdot p_2} \cdot ... \cdot d_k^{B\cdot p_k}$ y podemos calcular la suma de divisores usando la fórmula de arriba, $S = \prod_{i=1}^{k}\frac{d_i^{B\cdot p_i+1} - 1}{d_i -1}$ .

Si $d_i\not \equiv 1 \pmod{10^9+7}$ , entonces podemos calcular el valor de la expresión $\frac{d_i^{B\cdot p_i+1} - 1}{d_i -1}\pmod{10^9+7}$ usando exponenciación modular e inverso modular. En caso contrario, la expresión vale $1+d_i + d_i^2 + ... + d_i^{B\cdot p_i}\equiv B\cdot p_i+1\pmod{10^9+7}$ .

Sí necesitamos calcular los factores primos de $A$ , pero afortunadamente esto se puede hacer en tiempo $\mathcal{O}(\sqrt{A})$ .

Como $B$ puede ser tan grande como $10^{18}$ , para evitar desbordamientos podemos usar la función $\varphi$ de Euler y exponenciación binaria para calcular las potencias módulo $10^9+7$ .

Implementación

Complejidad temporal: $\mathcal{O}(\sqrt{A}+\log A\cdot \log B)$

C++


#include <fstream>
 
using namespace std;
 
#define ll long long
 
const int MOD = 1e9 + 7;
 
// BeginCodeSnip{Binary Exponentiation}
ll pow(ll a, ll b, ll m) {
	ll res = 1;
	a %= m;  // para evitar desbordamientos cuando a > 1e9
	while (b) {
		if (b & 1) { res = (res * a) % m; }
		a = (a * a) % m;
		b /= 2;
	}
	return res;
}
 
// EndCodeSnip
 
int main() {
	ifstream fin("sumdiv.in");
	ll a, b;
	fin >> a >> b;
 
	ofstream fout("sumdiv.out");
	if (b == 0) {
		fout << '1' << '\n';  // a^0 = 1
	} else {
		ll ans = 1;
		for (ll i = 2; i * i <= a; i++) {
			if (a % i == 0) {
				// si i divide a entonces en este caso siempre es primo
				// hallamos la potencia máxima de i que divide a a.
				ll co = 0;
				while (a % i == 0) {
					co++;
					a /= i;
				}
				// hallamos el valor de d - 1 y (d^k - 1) módulo (10^9 + 7).
				ll d_1 = pow(i - 1, MOD - 2, MOD);
				ll dk_1 =
				    (pow(i, (co * (b % (MOD - 1)) + 1) % (MOD - 1), MOD) - 1 + MOD) %
				    MOD;
				ans = (ans * ((d_1 * dk_1) % MOD)) % MOD;
			}
		}
 
		if (a > 1 && ((a - 1) % MOD) != 0) {
			// si a es mayor que 1 y a - 1 no es divisible por 10^9 + 7
			// hallamos el valor de d - 1 y (d^k - 1) módulo (10^9 + 7).
			ll d_1 = pow(a - 1, MOD - 2, MOD);
			ll dk_1 = (pow(a, (b + 1) % (MOD - 1), MOD) - 1 + MOD) % MOD;
			ans = (ans * ((d_1 * dk_1) % MOD)) % MOD;
		} else if (a > 1) {
			/*
			 * si a - 1 es divisible por 10^9 + 7,
			 * a es un primo de la forma k * (10^9 + 7) + 1.
			 * esto significa que la suma de a^i módulo (10^9 + 7), donde i va de 0 a b
			 * es (b + 1), así que multiplicamos por (b + 1).
			 */
			ans = (ans * ((b + 1) % MOD)) % MOD;
		}
 
		fout << ans << '\n';
	}
}