Quickest way to determine a polynomial with positive integer coefficients
Solution 1:
Ask for $m=p(1)$. Then all coefficients of $p$ are $\le m$. Ask for $M=p(m+1)$. Expand $M$ in base $m+1$, done. - That's two oracle queries and $\deg p$ integer div/mod operations
Solution 2:
Only $1$ input is needed to determine the polynomial: $\pi$. Since $\pi$ is transcendental, in principle we can figure out the polynomial from $f(\pi)$ (in a loose sense, none of the powers of $\pi$ can run into each other).
Note that this also works if we get rid of the positivity constraint.