A Fractional-Power Recurrence¶

Estimated time limit: 1.5 seconds. Memory limit: 128 MB.

The actual time limit is twice the slowest-case median runtime of the reference solution on the target judge, rounded up to a multiple of \(0.5\) seconds. See the benchmark environment.

Story¶

An evaluation service receives many integer queries. Each answer depends on answers at two smaller arguments. Compute the exact values for all queries.

(This story was rewritten by GPT-6.)

Formal Problem Statement¶

The function \(F\) maps nonnegative integers to nonnegative integers and satisfies

\[ F(x)=3F\left(\max\{\lfloor x^{4/5}\rfloor-1,0\}\right)+2F\left(\left\lfloor\frac{x}{2}\right\rfloor\right)+x \]

The fractional power is taken over the real numbers, and \(\lfloor\cdot\rfloor\) means floor. The equation also holds at zero, implying \(F(0)=0\) . Given \(N\) arguments \(a_i\) , compute each exact integer value \(F(a_i)\) without taking a modulus.

Input Format¶

The first line contains the query count \(N\) . The second contains \(a_1,\ldots,a_N\) .

Output Format¶

Print \(N\) space-separated integers on one line, giving answers in query order.

Samples¶

Sample 1¶

Input¶

5
0 1 1000000000 5000 2

Output¶

0 1 12422138161640 8422275 4

Sample 2¶

Input¶

6
0 0 1 2 3 4

Output¶

0 0 1 4 8 24

Sample Explanation¶

In the second sample, \(F(1)=1\) , \(F(2)=4\) , and \(F(3)=8\) . Since \(\lfloor4^{4/5}\rfloor-1=2\) , we have \(F(4)=3F(2)+2F(2)+4=24\) . Repeated queries at zero all return zero.

Constraints and Guarantees¶

For all inputs, \(1\le N\le10^5\) and \(0\le a_i\le10^9\) . Queries may repeat.

Score share	Additional conditions
100%	None