[原创]HDU 5936 Difference [思维啊]【思维】
[原创]HDU 5936 Difference [思维啊]【思维】
2017-03-25 16:34:26 Tabris_ 阅读数：551
博客爬取于 2020-06-14 22:41:07
以下为正文
版权声明：本文为 Tabris 原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/65937719
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5936
————————————————————————————————————————————
Difference
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 733 Accepted Submission(s): 192
Problem Description
Little Ruins is playing a number game, first he chooses two positive integers y and K and calculates f(y,K), here
f(y,K)=∑_{z\ in\ every\ digits\ of\ y}z^K(f(233,2)=2^2+3^2+3^2=22)
then he gets the result
x=f(y,K)−y
As Ruins is forgetful, a few seconds later, he only remembers K, x and forgets y. please help him find how many y satisfy\ x=f(y,K)−y.
Input
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
Output
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.
Sample Input
2
2 2
3 2
Sample Output
Case #1: 1
Case #2: 2
————————————————————————————————————————————
题目大意：
就是给你 k,x，问 y 的可能数
解题思路：
首先看到这个题实在没有好的想法，后发现，f(y,k)最大也不过f(999999999,9)，这样也才不到 10 位，
但是即使这样 还是不太好找 后想到将这 10 位分成前 5 位和后 5 位，预处理出来然后就行匹配，
这个匹配我们有很多种方法搞了，
首先在预处理的时候进行排序，在前 5 位时注意要 f(y,k)-y*100000\ 后 5 位f(y,k)-y\ 即可
那么就是找两集合的元素加和为 x 的方案数了，
可以枚举一个来二分另一个， O(100000\log(100000))\
也可以对一个从前找，另一个从后找，(双指针法) O(100000*2)\
代码注意细节就好
