시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB6272359726.575%

문제

자연수 N이 주어졌을 때, N의 각 자리수를 K제곱 한 후에 그 합을 구하는 함수를 SK(N)이라고 하자. 예를 들어, S2(65) = 62 + 52 = 61이다.

이제 다음과 같은 수열을 하나 만들어보자. N, SK(N), SK(SK(N)), … 이때, A와 B와 K가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 모든 N으로 각각 수열을 만들었을 때, 그 수열에서 가장 작은 수의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, K가 주어진다.

출력

첫째 줄에 문제의 정답을 출력한다.

제한

  • 1 ≤ A ≤ B ≤ 1,000,000
  • 1 ≤ K ≤ 6

예제 입력 1

1 5 2

예제 출력 1

14
  • 1: 1, 1, 1...
  • 2: 2, 4, 16, 37, 58, 89, 145, 42, 20, 4...
  • 3: 3, 9, 81, 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37...
  • 4: 4, 16, 37, 58, 89, 145, 42, 20, 4...
  • 5: 5, 25, 29, 85, 89, 145, 42, 20, 4, 16, 37, 58, 89...

예제 입력 2

13 13 2

예제 출력 2

1

예제 입력 3

10 99 1

예제 출력 3

450

예제 입력 4

535 538 3

예제 출력 4

820

예제 입력 5

100000 400000 6

예제 출력 5

5169721292

출처