방정식

시간 제한1초메모리 제한256 MB

요약

a 이상 b 이하인 정수 n 가운데 k 곱하기 n의 각 자리 제곱의 합이 n과 같은 것의 개수를 센다. a와 b는 10^18까지다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 수학, 완전 탐색, 구현
정답자: 아직 제출이 없습니다

문제

양의 정수 $n$ 에 대해 $f(n)$ 을 $n$ 의 십진법 표기에서 각 자릿수의 제곱의 합이라고 하자. 세 정수 $k, a, b$ 가 주어진다. $a \le n \le b$ 이면서 $n$ 이 방정식 [ k\cdot f(n) = 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$ 뿐이다.

예제1

예제 1
입력
```
51 5000 10000
```
예상 출력
```
3
```