Explanation

For an integer $A$, the sum of all divisors of the $A$ can be efficiently computed using the divisor function.

The formula states that if $d_1^{p_1} \cdot d_2^{p_2} \cdot ... \cdot d_k^{p_k}$ is the prime factorization of $A$, then the divisors' sum is:

For this problem we need to compute sum of divisors of $A^B$. If the prime factorization of $A$ is $d_1^{p_1} \cdot d_2^{p_2} \cdot ... \cdot d_k^{p_k}$ then the prime factorization of $A^B$ will be $d_1^{B\cdot p_1} \cdot d_2^{B\cdot p_2} \cdot ... \cdot d_k^{B\cdot p_k}$ and we can compute the sum of divisors using the above formula, $S = \prod_{i=1}^{k}\frac{d_i^{B\cdot p_i+1} - 1}{d_i -1}$.

If $d_i\not \equiv 1 \pmod{10^9+7}$, then we can compute the value of the expression $\frac{d_i^{B\cdot p_i+1} - 1}{d_i -1}\pmod{10^9+7}$ using modular exponentiation and modular inverse. Otherwise, the expression equals $1+d_i + d_i^2 + ... + d_i^{B\cdot p_i}\equiv B\cdot p_i+1\pmod{10^9+7}$.

We do need to compute the prime factors of $A$, but thankfully this can be done in $\mathcal{O}(\sqrt{A})$ time.

Since, $B$ can be as large as $10^{18}$, to avoid overflows we can use Euler's totient function and binary exponentiation to compute the powers modulo $10^9+7$.

Implementation

Time Complexity: $\mathcal{O}(\sqrt{A}+\log A\cdot \log B)$

Copy
#include <fstream>

using namespace std;

#define ll long long

const int MOD = 1e9 + 7;

 Code Snippet: Binary Exponentiation (Click to expand)