P15802 [GESP202603 Level 7] Splitting

Related multiple-choice and true/false problems: .

Xiao A wants to split a positive integer $n$ into the sum of several positive integers, and maximize the product of the integers after splitting. Xiao A hopes you can help him compute the maximum possible product. Since the answer may be very large, you only need to output the result modulo $10^9$. Formally, a split of $n$ is a set of positive integers $a_1,\dots,a_k$ such that $a_1+\cdots+a_k=n$, where $1\leq k\leq n$. You need to output, among all splits of $n$, the maximum value of $a_1\times \cdots\times a_k$ modulo $10^9$.

The first line contains a positive integer $t$, the number of test cases. For each test case: one line containing an integer $n$, the given positive integer.

For each test case: output one line containing an integer, the maximum product after splitting $n$ modulo $10^9$.

For $40\%$ of the test cases, it is guaranteed that $n\leq 50$. For all test cases, it is guaranteed that $1\leq t\leq 10^4$ and $1\leq n\leq 10^6$. Translated by ChatGPT 5