P1771 Solutions to the Equation

Jiajia ran into a tough problem and asks you to help solve it. Consider the Diophantine equation $a_1 + a_2 + \cdots + a_{k-1} + a_k = g(x)$, where $k \ge 2$ and $k \in \mathbb{N}^*$, $x$ is a positive integer, and $g(x) = x^x \bmod 1000$ (that is, the remainder of $x^x$ modulo $1000$). The numbers $x$ and $k$ are given. Your task is to find the number of solution tuples in positive integers to this equation. For example, when $k = 3, x = 2$, the solutions are: $$\begin{cases} a_1=1\\ a_2=1\\ a_3=2 \end{cases}$$ $$\begin{cases} a_1=1\\ a_2=2\\ a_3=1 \end{cases}$$ $$\begin{cases} a_1=2\\ a_2=1\\ a_3=1 \end{cases}$$

The input contains exactly one line with two positive integers separated by a space, namely $k, x$.

Output exactly one line with the number of solution tuples in positive integers.

- For 40% of the testdata, $\mathit{ans} \le 10^{16}$. - For 100% of the testdata, $k \le 100$, $x \le 2^{31}-1$, $k \le g(x)$. NOI Journal 2010 Senior (01) Translated by ChatGPT 5