← All solutions

Shortest judge solution: 1241 bytes. Shortest team solution (during contest): 841 bytes.

This problem is not very hard but requires a small leap of faith (or good number-theoretic intuition).

Given a number k with prime factorization p₁^e₁ p₂^e₂ . . . p_t^e_t , the first observation is that the number of arrangements f (k ) of the prime factors is the multinomial number (e₁+...+e_t)/(e₁,e₂,...,e_t) = (e₁+...+e_t)!/(e₁!e₂!...e_t! ). Given the numbers e₁ , . . . , e_t , this is easily computed (though some care has to be taken to avoid overflow).

Note that permuting the exponents e_i or changing the values of the primes p_i does not change the value of f (k ). Since we are looking for the smallest k with the given value of f (k ), this implies that we may without loss of generality restrict attention to numbers of the form e₁ ≥ e₂ ≥ . . . ≥ e_t and that p_i is the i’th prime (i.e., p₁ = 2, p₂ = 3, p₃ = 5, and so on).

In other words, we can try to generate all numbers k that are of the form k = 2^e₁ 3^e₂ 5^e₃ . . . satisfying e₁ ≥ e₂ ≥ e₃ ≥ . . . and 1 < k < 2⁶³ . It turns out that there are exactly 43606 such numbers, so this can be done quickly. For each such number we compute f (k ) and check if it is less than 2⁶³ , and then construct a lookup table which for each possible value of f (k ) (it turns out there are 19274 of them) gives the smallest preimage k.

Apart from overflows, there is only one corner case, namely n = 1, for which the answer is k = 2 (since the problem requires k > 1). Fortunately, this case was covered as the first sample data. Unfortunately, many teams didn’t seem to notice this, and submitted solutions that failed on the sample data...