P1771 方程的解

admin

https://www.luogu.com.cn/problem/P1771

题目描述

佳佳碰到了一个难题，请你来帮忙解决。对于不定方程 a1+a2+....+ak=g(x)其中k≥2 ，x 是正整数，g(x)=x^x%1000(即 x^x除以 1000 的余数)，x,k 是给定的数。我们要求的是这个不定方程的正整数解组数。

举例来说，当 k=3,x=2 时，方程的解分别为：(1 1 2) (1 2 1) (2 1 1)三组。
输入格式
输入文件equation.in有且只有一行，为用空格隔开的两个正整数，依次为k，x。

输出格式
输出文件equation.out有且只有一行，为方程的正整数解组数。

输入输出样例
输入 #1复制
3 2
输出 #1复制
3
说明/提示
对于40%的数据，ans≤10^16；对于100%的数据，k≤100，x≤2^31-1，k≤g(x)。

_NOI导刊2010提高（01）