Karim Meets Gollum

Solution 1:

1. Sieve until $\lceil{\sqrt{\textit{MAXN}}}\rceil$ and save all the primes in a list which has a complexity of $O(\sqrt{\textit{MAXN}}\ln{\ln{\sqrt{\textit{MAXN}}}})$\
2. For each query, prime factorize the $N$ by iterating over the list. The complexity for this is $O(\pi(\sqrt{\textit{MAXN}})$. This will at worst case take $5761455$ iterations per query.\
3. For each prime factor $p$, find it's multiplicity $\alpha$ \
4. Then compute $s(p,\alpha) = \sum_{i=0}^{\alpha} p^{K\dot i} \textbf{ mod} (10^9+7)$, this can be done in $O(\lg{K} + \lg{\alpha}) $ or $O(\lg{K} + \alpha) $ \
5. Now the answer to each query can be expressed as the product of $s$ for each prime factor $p$ of $N$. So, it will take us $O(\lg{K} \times \lg{N} + \lg{N})$ to compute this. (Since there can be at most $\lg{N}$ prime factors and sum of all the $\alpha$ is bounded by $\lg{N}$\
6. So the final complexity is $O(\sqrt{\textit{MAXN}}\ln{\ln{\sqrt{\textit{MAXN}}}} + Q \times ((1+\lg{\textit{MAXK}}) \times \lg{\textit{MAXN}} + \pi(\sqrt{\textit{MAXN}})))$.