Let \(m\) be a positive integer. Find, in terms of \(m\), all polynomials \(P(x)\) with integer coefficients such that for every integer \(n\), there exists an integer \(k\) such that \(P(k)=n^m\).

[i]Proposed by Raymond Feng[/i]
1. **Initial Setup and Simplification:**
   Let \( n = 0 \). Then, there exists an integer \( k_0 \) such that \( P(k_0) = 0 \). This implies that \( k_0 \) is a root of \( P(x) \). 
   
   Since \( P(x) \) has integer coefficients, if \( P(x) \) works, then \( P(x + c) \) also works for any integer \( c \). Define \( Q(x) = P(x + k_0) \). Then \( Q(0) = P(k_0) = 0 \), which implies \( x \mid Q(x) \). Therefore, we can write \( Q(x) = x^\ell R(x) \) for some polynomial \( R(x) \) with integer coefficients and some integer \( \ell \geq 1 \).

2. **Claim and Proof:**
   **Claim:** If \( Q(x) = x^\ell R(x) \) for a polynomial \( R(x) \) with integer coefficients and an integer \( \ell \geq 1 \), then \( Q(x) = \pm x^\ell \) or \( Q(x) = x^{\ell+1} R_1(x) \) for some polynomial \( R_1(x) \) with integer coefficients.
   
   **Proof:** Consider a prime \( p \). There exists an integer \( k \) such that \( Q(k) = p^m \). Since \( Q(x) = x^\ell R(x) \), we have \( k^\ell R(k) = p^m \). This implies \( k \mid p^m \), so let \( k = \pm p^t \). Then, \( R(p^t) = \pm p^{m - \ell t} \).
   
   Let \( R(x) = a_s x^s + a_{s-1} x^{s-1} + \cdots + a_1 x + a_0 \). Then,
   \[
   a_s p^{ts} + a_{s-1} p^{t(s-1)} + \cdots + a_1 p^t + a_0 = \pm p^{m - \ell t}.
   \]
   For this to hold, one or more of the following must be true:
   - \( t = 0 \)
   - \( m = \ell t \)
   - \( p \mid a_0 \)
   
   Varying \( p \), we see that \( t = 0 \) is true at most once, as it implies \( Q(1) = p^m \), which occurs for at most one \( p \). Suppose \( p \mid a_0 \) is true finitely many times as \( p \) varies. Then, \( m = \ell t \) infinitely many times, implying \( R(p^t) = \pm 1 \) infinitely many times. Hence, either \( R(x) - 1 \) or \( R(x) + 1 \) has infinitely many roots, so \( R(x) = \pm 1 \). Therefore, \( Q(x) = \pm x^\ell \).

3. **Induction on Degree:**
   Let \( \deg Q = d \). We claim by induction that for positive integers \( z \leq d \), we can write \( Q(x) = x^z R_z(x) \) where \( R_z(x) \) is a polynomial with integer coefficients.
   
   - **Base Case:** For \( z = 1 \), we proved earlier that \( x \mid Q(x) \).
   - **Inductive Step:** Assume \( Q(x) = x^y R_y(x) \) for some \( y \) where \( y + 1 \leq d \). By our claim, \( Q(x) = x^{y+1} R_{y+1}(x) \) or \( Q(x) = \pm x^y \). The latter is false by degree comparison. Hence, our induction is complete, so we can let \( Q(x) = x^d R_d(x) \). Applying our claim, we have \( Q(x) = \pm x^d \) or \( Q(x) = x^{d+1} R_{d+1}(x) \). Again, the latter case is false by degrees.

4. **Conclusion:**
   Suppose \( d \mid m \). Then, letting \( n = 2 \), we have \( \pm k^d = 2^m \) for some \( k \). Note \( k = \pm 2^a \), so \( \pm 2^{ad} = 2^m \), implying \( ad = m \), a contradiction. Hence, \( Q(x) = \pm x^d \) where \( d \mid m \). Note if \( d \) is odd, both plus and minus work, but if \( d \) is even, only plus works (or else \( Q \) can't cover positive values). Hence, \( Q(x) = (\pm x)^d \), so \( P(x) = (\pm x + c)^d \). This works if we let \( x = n^{m/d} \mp c \).

The final answer is \( \boxed{ P(x) = (\pm x + c)^d } \) where \( d \mid m \).