HDU 5936 Difference

题意：
有一个函数f(y, k) = y的每个十进制位上的数字的k次幂之和
给x, k 求有多少个y满足 x = f(y, k) - y

思路：
(据说这叫中途相遇法？)
由于 x >= 0 所以显然y最多也不会超过10位数
把一个数拆成前5位和后5位
即找有多少对(a, b)满足 x = a + b
把所有的后五位预处理出来，然后再找前五位。
找的时候用二分，mapT了。。可能组数太多了吧。

具体看代码

 1 const int maxn = 100000 + 10;
 2 
 3 LL num[maxn];
 4 int x, k;
 5 LL p[10][10];
 6 LL sum[maxn];
 7 int idx;
 8 
 9 void init()
10 {
11     memset(sum, 0, sizeof(sum));
12     idx = 0;
13 
14     scanf("%d%d", &x, &k);
15     for (int i = 1; i < 100000; i++)
16     {
17         int t = i;
18         while (t)
19         {
20             sum[i] += p[t % 10][k];
21             t /= 10;
22         }
23         num[idx++] = sum[i] - i;
24     }
25     sort(num, num + idx);
26 }
27 
28 void solve()
29 {
30     LL t = 0;
31     LL ans = 0;
32     for (LL i = 0; i < 100000; i++)
33     {
34         t = sum[i] - i * 100000;
35         int f = lower_bound(num, num + idx, x - t) - num;
36         while (num[f] == x - t && f < idx) 
37         {
38             f++;
39             ans++;
40         }
41     }
42     printf("%lld
", ans);
43 }
44 
45 int main()
46 {
47     for (int i = 1; i < 10; i++)
48     {
49         p[i][0] = 1;
50         for (int j = 1; j < 10; j++)
51         {
52             p[i][j] = p[i][j-1] * i;
53         }
54     }
55     int T, kase = 0;
56     scanf("%d", &T);
57     while (T--)
58     {
59         printf("Case #%d: ", ++kase);
60         init();
61         solve();
62     }
63     return 0;
64 }