eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Розширене щасливе число (Topcoder, SRM 334)

Розширене щасливе число (Topcoder, SRM 334)

Ліміт часу 3 секунди
Ліміт використання пам'яті 64 MiB

Дано натуральне число n. Піднесемо до k - го степеня кожну його цифру та просумуємо отримані результати. Позначимо результат через S_k(n). Наприклад, S_2(65) = 6^2 + 5^2 = 61. Побудуємо послідовність n, S_k(n), S_k(S_k(n)), … .

Щастям числа n по відношенню до k будемо називати найменше число у цій послідовності.

Вхідні дані

Кожний рядок є окремим тестом і містить три цілі числа a, b (1 a, b10^6) та k (1 k6).

Вихідні дані

Для кожного тесту обчислити щастя для кожного числа від a до b включно по відношенню до k і вивести їх суму.

Приклад

Вхідні дані #1
13 13 2
1 5 2
535 538 3
Вихідні дані #1
1
14
820