#P1771. 方程的解

    ID: 800 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划dp数论数学高精度递归NOI 导刊

方程的解

题目描述

佳佳碰到了一个难题,请你来帮忙解决。对于不定方程 a1+a2++ak1+ak=g(x)a_1+a_2+\cdots +a_{k-1}+a_k=g(x),其中 k2k\ge 2kNk\in \mathbb{N}^*xx 是正整数,g(x)=xxmod1000g(x)=x^x \bmod 1000(即 xxx^x 除以 10001000 的余数),x,kx,k 是给定的数。我们要求的是这个不定方程的正整数解组数。

举例来说,当 k=3,x=2k=3,x=2 时,方程的解分别为:

{a1=1a2=1a3=2\begin{cases} a_1=1\\ a_2=1\\ a_3=2 \end{cases} {a1=1a2=2a3=1\begin{cases} a_1=1\\ a_2=2\\ a_3=1 \end{cases} {a1=2a2=1a3=1\begin{cases} a_1=2\\ a_2=1\\ a_3=1 \end{cases}

输入格式

输入有且只有一行,为用空格隔开的两个正整数,依次为 k,xk,x

输出格式

输出有且只有一行,为方程的正整数解组数。

3 2
3

提示

  • 对于 40%40\% 的数据,ans1016\mathit{ans} \le 10^{16}
  • 对于 100%100\% 的数据,k100k \le 100x2311x \le 2^{31}-1kg(x)k \le g(x)

NOI导刊2010提高(01)