방정식

시간 제한2초메모리 제한512 MB

요약

a 이상 b 이하인 양의 정수 n 가운데 각 자릿수의 제곱합에 k를 곱한 값이 n과 같은 것의 개수를 센다.

문제

자연수 $n$ 에 대해 $f(n)$ 은 $n$ 을 십진법으로 썼을 때 각 자리 숫자의 제곱의 합으로 정의한다. 세 자연수 $k, a, b$ 가 주어진다. $a \le n \le b$ 이면서 $n$ 이 다음 방정식의 해가 되는 자연수 $n$ 의 개수를 구하시오.

$k \cdot f(n) = n$

첫째 줄이자 유일한 줄에 문제에 나온 세 정수 $k, a, b$ 가 주어진다. ( $1 \le k, a, b \le 10^{18}$ , $a \le b$ )

프로그램은 구간 $[a, b]$ 에서 방정식의 해의 개수를 나타내는 정수 하나를 출력해야 한다.

$k = 51$ 일 때 구간 $[5000, 10000]$ 에서 방정식을 만족하는 자연수 $n$ 은 7293, 7854, 7905뿐이다.