smallest K such that number of arrangements of prime factors of K equals N?
Разница между en5 и en6, 125 символ(ов) изменены
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?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский pabloskimg 2018-10-29 20:56:46 125
en5 Английский pabloskimg 2018-10-29 20:46:41 4 Tiny change: 'r)!}{k_1! + ... + k_r!} < 2' -> 'r)!}{k_1! * ... * k_r!} < 2'
en4 Английский pabloskimg 2018-10-29 20:45:40 605 Tiny change: '_r$ ($k_i >= k_j$ for ' -> '_r$ ($k_i \geq k_j$ for '
en3 Английский pabloskimg 2018-10-28 19:15:30 30 Tiny change: 'ficiently.' -> 'ficiently.\n\nUPDATE: why the downvotes?'
en2 Английский pabloskimg 2018-10-27 17:43:02 1
en1 Английский pabloskimg 2018-10-27 17:41:36 227 Initial revision (published)