Basically the title. The problem statement can be found [here](https://uva.onlinejudge.org/external/15/p1575.pdf). No idea how to solve it efficiently.↵
↵
UPDATE 1: why the downvotes?↵
↵
UPDATE 2: based on the answers so far, the solution would be to exhaustively explore all combinations of exponents $k_1$, $k_2$, ..., $k_r$ ($k_i \geq k_j$ for all $i < j$) such that $n = \frac{(k_1 + ... + k_r)!}{k_1! * ... * k_r!} < 2^{63}$ and $ k = 2^{k_1} * 3^{k_2} * 5^{k_3} * 7^{k_4} * 11^{k_5} * ... < 2^{63}$. During the exhaustive search one can map each n to its minimum k found (for instance, using an unordered_map) and then the queries can be answered in O(1). The problem is: how can you estimate the complexity of the exhaustive search? Any easy way to estimate an upperbound for it?↵
↵
UPDATE 3: pshishod2645 says there are around $2*10^6$ valid combinations of exponents, where did he get that number from?
↵
UPDATE 1: why the downvotes?↵
↵
UPDATE 2: based on the answers so far, the solution would be to exhaustively explore all combinations of exponents $k_1$, $k_2$, ..., $k_r$ ($k_i \geq k_j$ for all $i < j$) such that $n = \frac{(k_1 + ... + k_r)!}{k_1! * ... * k_r!} < 2^{63}$ and $ k = 2^{k_1} * 3^{k_2} * 5^{k_3} * 7^{k_4} * 11^{k_5} * ... < 2^{63}$. During the exhaustive search one can map each n to its minimum k found (for instance, using an unordered_map) and then the queries can be answered in O(1). The problem is: how can you estimate the complexity of the exhaustive search? Any easy way to estimate an upperbound for it?↵
↵
UPDATE 3: pshishod2645 says there are around $2*10^6$ valid combinations of exponents, where did he get that number from?
