Simons and Cakes for Success

Research check: the official Codeforces Round 1083 editorial for 2205B confirms the intended route: use the prime factorization of $n$, prove the minimum $k$ is the product of distinct prime factors, and compute it by trial division in $O(\sqrt n)$: https://codeforces.com/blog/entry/151310. I also checked it against the supplied statement and samples; the statement is the source of truth here.

Let

$$n=\prod_{i=1}^{m} p_i^{a_i}$$

be the prime factorization of $n$.

We need the smallest positive integer $k$ such that

$$n\mid k^n.$$

Think in prime exponents. If prime $p_i$ appears in $k$ with exponent $b_i$, then in $k^n$ it appears with exponent

$$n b_i.$$

For $n$ to divide $k^n$, every prime power from $n$ must be covered, so for every $i$:

$$n b_i \ge a_i.$$

Now the important part: if $p_i$ divides $n$ but does not divide $k$, then $b_i=0$, so $n b_i=0<a_i$. Divisibility fails. So every distinct prime factor of $n$ must appear in $k$ at least once.

That gives a lower bound:

$$k \text{ must be divisible by } \prod_{i=1}^{m} p_i.$$

Now prove that this lower bound is actually enough. Let

$$k=\prod_{i=1}^{m} p_i.$$

Then

$$k^n=\prod_{i=1}^{m} p_i^n.$$

So each prime $p_i$ has exponent $n$ inside $k^n$. Since $p_i^{a_i}\mid n$ and $n\ge2$, we have $a_i\le n$. Therefore

$$p_i^{a_i}\mid p_i^n.$$

This is true for every prime factor, so

$$n=\prod_{i=1}^{m}p_i^{a_i}\mid \prod_{i=1}^{m}p_i^n=k^n.$$

So the product of distinct prime divisors is valid, and since every valid $k$ must contain those primes, it is minimal. No need to build $k^n$ or do giant-number nonsense. That would be deeply unnecessary suffering.

Algorithm:

1. Set ans = 1 and x = n.
2. Try every divisor $d$ from $2$ while $d^2\le x$.
3. If $d\mid x$, multiply ans by $d$ once.
4. Divide all copies of $d$ out of x.
5. After the loop, if x > 1, then x is one remaining prime factor, so multiply ans by x.

Why the leftover is prime: after all smaller factors are removed, if the remaining x were composite, it would have some factor at most $\sqrt{x}$, and the loop would not have missed it.

Edge cases:

• If $n$ is prime, no divisor is found, and the leftover x=n becomes the answer.
• If $n$ is a prime power like $8=2^3$, multiply by $2$ once and remove all copies.
• If $n$ has a large prime factor, it remains as the final x > 1.

Complexity per test case:

$$O(\sqrt n)$$

with $O(1)$ memory. For $n\le10^9$ and $t\le100$, this is totally fine.