方程

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 equationz.in 输出文件 equationz.out

【题目描述】

hyc 碰到了一个难题,请你来帮忙解决。

对于不定方程a1+a2+a3+……+ak=g(x) ,其中K.>=2,k是正整数 , x 是正整数 ,

g(x)=x^x mod 1000 , x,k 是给定的数 . 我们要求的是这个不定方程的正整数解组数 .

举例来说 , 当 k=3,x=2 时 ,g(x)=4, 原方程即 A1+A2+A3=4 .

这个方程的正整数解有 3 组 . 分别为 (A1,A2,A3) = (2,1,1),(1,2,1),(1,1,2).

【输入文件】

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

【输出文件】

有且只有一行 , 为方程的正整数解组数 .

【样例输入】

3 2

【样例输出】

3

【数据范围】

对于 40% 的数据 , ans<= 10^16 ;

对于 100% 的数据 , k<=100 , x<= 2^31-1 ,k<=g(x)。