This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
$S_K(N)$は$N$の各桁を$K$乗した和と定義される．$S_2(65) = 6 ^2 + 5 ^2 = 61$である．$N$に対する数列は
$$
[N, S_K(N), S_K (S_K (N) ), …]
$$
と定義される．$N$, $K$が与えられた時の$happiness$は数列の中の最小値である．$A, B, K$が与えられるので，$A \sim B$の各$happiness$の和を求める．
$A \sim B$のそれぞれの数について数列を求めるが，別の数列を求めていたとしても同じ数が途中に出現すればそれ以降は同じになるので，これをメモ化する．内容はその後の最小値である．最大値は$N = 999999, K = 6$の$2125764$であるが十分に余裕を持って配列を持った．後はそれぞれについて$happiness$を求め，その和を答える．
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
using namespace std ;
typedef long long ll ;
typedef pair < int , int > P ;
ll memo [ 5000005 ], k ;
ll f ( ll x ) {
ll ret = 0 ;
while ( x ) {
ll y = ( x % 10 ), t = 1 ;
rep ( i , k ) {
t *= y ;
}
ret += t ;
x /= 10 ;
}
return ret ;
}
ll dfs ( ll x ) {
if ( memo [ x ] != - 1 ) {
if ( memo [ x ] == INF ) {
ll y = x , res = x ;
while ( true ) {
y = f ( y );
res = min ( res , y );
if ( y == x ) break ;
}
return memo [ x ] = res ;
} else return memo [ x ];
}
memo [ x ] = INF ;
ll res = min ( x , dfs ( f ( x )) );
return memo [ x ] = res ;
}
class ExtendedHappyNumbers {
public :
long long calcTheSum ( int A , int B , int K ) {
ll ans = 0 ;
memset ( memo , - 1 , sizeof ( memo ));
k = K ;
REP ( i , A , B + 1 ) {
ans += dfs ( i );
}
return ans ;
}
};