so fast

2ⁿ since the inclusion-exclusion formula is used in the proof. But it is only the proof that the main function is a polynomial, we don't need to actually compute all these 2ⁿ summands.

I am not a setter of this problem, but I considered it to be OK when it was proposed. Perhaps it would be better if we didn't ask for a certificate.

But I still don't quite understand why it received such an amount of hate. There are problems which at first seem like handling a lot of corner cases without applying any specific idea, but if contestant thinks carefully before starting to write code, then he can reduce the length of this solution and the number of cases he needs to handle. I understand how this problem can be seen as a bad one if someone picks the first solution idea that comes to his mind and starts implementing it right away, but is it a good strategy on contests?

same here , didn't got it either. Hope someone explains.

As $$$(x\ mod\ k)*(x\ div\ k)=n$$$, both $$$x\ mod\ k$$$ and $$$x\ div\ k$$$ should be the divisors of $$$n$$$.

As $$$k \leq 10^3$$$, which is very little, that means $$$x\ mod\ k$$$ is also less than $$$10^3$$$.

Therefore, we can try all possibilities of $$$x\ mod\ k$$$ by assigning all values from $$$0$$$ to $$$k-1$$$ that are divisors of $$$n$$$ to it.

Let $$$p$$$ be the assigned value of $$$x\ mod\ k$$$. How can we recover $$$x$$$?

As we know right away that $$$x\ div\ k = \frac{n}{p}$$$, $$$x$$$ is almost going to be $$$k\cdot \frac{n}{p}$$$. However, if it ends that way, $$$x\ mod\ k$$$ would be $$$0$$$ which might be contradiction as we assigned $$$x\ mod\ k$$$ to be $$$p$$$.

BUT $$$0 \leq p < k$$$. So if we add $$$p$$$ to that $$$x$$$, the $$$x\ div\ k$$$ wouldn't change and $$$x\ mod\ k$$$ is now $$$p$$$, the problem is solved.

In conclusion, $$$x$$$ must be $$$k\cdot \frac{n}{p}+p$$$ if $$$x\ mod\ k=p$$$