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了。。可能组数太多了吧。

具体看代码

 const int maxn =  + ;

 LL num[maxn];

 int x, k;

 LL p[][];

 LL sum[maxn];

 int idx;

 void init()

 {

     memset(sum, , sizeof(sum));

     idx = ;

     scanf("%d%d", &x, &k);

     for (int i = ; i < ; i++)

     {

         int t = i;

         while (t)

         {

             sum[i] += p[t % ][k];

             t /= ;

         }

         num[idx++] = sum[i] - i;

     }

     sort(num, num + idx);

 }

 void solve()

 {

     LL t = ;

     LL ans = ;

     for (LL i = ; i < ; i++)

     {

         t = sum[i] - i * ;

         int f = lower_bound(num, num + idx, x - t) - num;

         while (num[f] == x - t && f < idx)

         {

             f++;

             ans++;

         }

     }

     printf("%lld\n", ans);

 }

 int main()

 {

     for (int i = ; i < ; i++)

     {

         p[i][] = ;

         for (int j = ; j < ; j++)

         {

             p[i][j] = p[i][j-] * i;

         }

     }

     int T, kase = ;

     scanf("%d", &T);

     while (T--)

     {

         printf("Case #%d: ", ++kase);

         init();

         solve();

     }

     return ;

 }