005 - デュードニー数

時間制限 1 秒 / メモリ制限 256 MB / 得点 6 / x 16 /


TLE
1sec
MLE
256MB
得点
6

問題文

正の整数xの各桁をすべて足して得られる数の3乗がxになるとき、この数xをデュードニー数といいます。たとえば、512は8の3乗で、5+1+2 = 8 となるので512はデュードニー数です。

この問題では、デュードニー数と似た数を考えて、その個数を求めます。

課題

負でない整数a、2以上の整数n、および上限値mが与えられる。このとき、xの各桁をすべて足して得られる数yについて、x = (y+a)nとなるm以下の正の整数xの個数を出力するプログラムを作成せよ。

入力・出力

入力

入力は以下の形式で与えられる。

a n m

1行に、a(0≦a≦50)n(2≦n≦10)と上限値m(1000≦m≦108)が、すべて整数で与えられる。

時間制限

入力に対して、実行時間が8秒を超えてはならない。

出力

個数を1行に出力する。

入出力例

入力例 1

16 2 1000

出力例 1

2

400 = (4+0+0+16)2となる数400、841 = (8+4+1+16)2となる数、841の2つ。


入力例 2

0 3 5000

出力例 2

3

1 = 13となる数1、512 = (5+1+2)3となる数512、4913 = (4+9+1+3)3となる数4913の3つ。


入力例 3

2 3 100000

出力例 3

0

xの各桁をすべて足して得られる数yについて(y+2)3 = xとなるような 100,000 以下の数xはない。