자릿수 거듭제곱 수열
면접 대비시간 제한2초메모리 제한128 MB
A부터 B까지 각 N에 대해 자릿수의 K제곱 합을 반복 적용해 사이클을 찾고, 각 수열에서 나온 최솟값들의 합을 구하는 문제입니다.
문제
자연수 N에 대해 S_K(N)을 N의 각 십진수 자리수를 K제곱한 값들의 합이라고 하자. 예를 들어 S_2(65) = 6^2 + 5^2 = 61이다.
이제 수열 N, S_K(N), S_K(S_K(N)), ...을 만든다. 세 정수 A, B, K가 주어졌을 때, A <= N <= B인 모든 자연수 N에 대해 이 수열을 만들고, 각 수열에 등장하는 가장 작은 값을 구한다. 그 값들의 합을 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 세 정수 A, B, K가 주어진다.
출력
첫째 줄에 정답을 출력한다.
제한
1 <= A <= B <= 1,000,0001 <= K <= 6