<h1 id="heading">题目</h1>
<blockquote>
<h2 id="description">Description</h2>
<blockquote>
Little Ruins is playing a number game, first he chooses two positive integers y and K and calculates f(y,K), here
<code>f(y,K) = ∑in every digits of y zK</code> <code>(f(233,2) = 22+32+32=22)</code>
then he gets the result
<code>x=f(y,K)-y</code>
As Ruins is forgetful, a few seconds later, he only remembers K, x and forgets y. please help him find how many y satisfy <code>x=f(y,K)-y</code>.
 
</blockquote>
<h2 id="input">Input</h2>
<blockquote>
First line contains an integer T, which indicates the number of test cases.
Every test case contains one line with two integers x, K.
Limits 
1≤T≤100 
0≤x≤109 
1≤K≤9
</blockquote>
<h2 id="output">Output</h2>
<blockquote>
For every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the result.
</blockquote>
<h2 id="sample-input">Sample Input</h2>
<blockquote>
2 
2 2 
3 2
</blockquote>
<h2 id="sample-output">Sample Output</h2>
<blockquote>
Case #1: 1 
Case #2: 2
</blockquote>
</blockquote>
<h1 id="heading-1">题解</h1>
求所有满足 <code>x=f(y,K)-y</code> 的数量 
计算一下,可以发现 y 最多为 10 位 (计算下极端情况) 
而暴力搜索 10 位的数字显然会超时 
可以采用 中途相遇法 的思路,将 10 位数字分成两个 5 位 
然后分别计算两部分,再对两部分进行比较即可
首先可以知道, <code>f(y,K)</code> 函数是一个有确定的函数,因此可以打表直接查询结果 
而每次需要求的 <code>zK</code> 也是有确切结果的,也可以打表(对于这道题,不打表时间会多很多)
将 <code>x=f(y,K)-y</code> 化成 <code>x=f(a,K)+f(b,K)-a*100000-b</code> 其中 <code>a</code> <code>b</code> 分别是 <code>y</code> 的前 5 位和后 5 位 
可以看出, <code>f(a,K)-a*100000</code> 和 <code>f(b,K)-b</code> 可以分别在自己的循环里计算
用一个数组来记录第一个循环能得到的结果,在第二个循环里累计其结果在第一个循环里的数量 
(用 map 会超时,可以用 <code>lower_bound()</code> 和 <code>upper_bound()</code> 快速求个数)
特别注意,如果 <code>x=0</code> 在两个循环会被重复计算 1 次,因此要额外 <code>-1</code>
代码量不大,思路也比较容易理解,注意各种打表优化即可
<h1 id="heading-2">代码</h1>
<pre style="background-color:#fff">//#include &lt;ctime&gt;
//#define debug

#include &lt;cstdio&gt;
#include &lt;iostream&gt;
#include &lt;map&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;
#include &lt;cstring&gt;

using namespace std;

typedef long long LL;

LL List[100005][10];
LL Pre[100005];
int pw[10][10];

int Pow(int a,int n) {
 if(pw[a][n] == -1){
 if(n == 1) pw[a][n] = a;
 else if(n == 0) pw[a][n] = 1;
 else pw[a][n] = Pow(a,n / 2) * Pow(a,n - n / 2);
 }
 return pw[a][n];
}

inline LL f(LL y,int k) {
 // if(List[y][k] == -1) {
 // LL sum = 0;
 // while(y) {
 // sum += Pow((int)(y % 10),k);
 // y /= 10;
 // }
 // List[y][k] = sum;
 // }
 return List[y][k];
}

int lower_bound(LL *arr,int size, LL key) {
 int half;
 int mid;
 int first = 0;
 while (size &gt; 0) {
 half = size &gt;&gt; 1;
 mid = first + half;
 if (arr[mid] &lt; key) {
 first = mid + 1;
 size = size - half - 1;
 } else {
 size = half;
 }
 }
 return first;
}
int upper_bound(LL *arr,int size, LL key) {
 int mid;
 int first = 0;
 int half;
 while (size &gt; 0) {
 half = size &gt;&gt; 1;
 mid = half + first;
 if (arr[mid] &gt; key) {
 size = half;
 } else {
 first = mid + 1;
 size = size - half - 1;
 }
 }
 return first;
}

inline int Count(LL pre) {
 return upper_bound(Pre,100000,pre) - lower_bound(Pre,100000,pre);
}

int main() {
 #ifdef debug
 freopen(&#34;in.txt&#34;,&#34;r&#34;,stdin);
 int start = clock();
 #endif

 cin.tie(0);
 cin.sync_with_stdio(false);

 int T;
 cin &gt;&gt; T;
 //scanf(&#34;%d&#34;,&amp;T);

 memset(pw,-1,sizeof(pw));

 for(int i=0;i&lt;100000;i++){
 for(int j=1;j&lt;=9;j++){
 LL sum = 0;
 int y = i;
 while(y) {
 sum += Pow((int)(y % 10),j);
 y /= 10;
 }
 List[i][j] = sum;
 }
 }
 //memset(List,-1,sizeof(List));

 for(int kase = 1;kase &lt;= T;kase++) {
 LL x;
 int k;
 cin &gt;&gt; x &gt;&gt; k;
 //scanf(&#34;%d%d&#34;,&amp;x,&amp;k);

 //前5位的各位k次方 - 前五位数据
 for(int i = 0;i &lt; 100000;i++) {
 LL pre = f(i,k) - (LL)i * 100000;
 Pre[i] = pre;
 }
 
 sort(Pre,Pre + 100000);
 LL cnt = 0;

 //后5位的各位k次方 - 后五位数据
 for(int i = 0;i &lt; 100000;i++) {
 LL post = f(i,k) - (LL)i;
 LL pre = x - post;
 cnt += Count(pre);
 }
 cout &lt;&lt; &#34;Case #&#34; &lt;&lt; kase &lt;&lt; &#34;: &#34; &lt;&lt; cnt-(x==0) &lt;&lt; endl;
 // printf(&#34;Case #%d: %d\n&#34;,kase,cnt);
 }

 #ifdef debug
 printf(&#34;Time:%.3lfs\n&#34;,double(clock() - start) / CLOCKS_PER_SEC);
 #endif

 return 0;
}
</pre>

HDU 5936.Difference(2016 CCPC 杭州 D)