题目

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) = ∑in every digits of y zK (f(233,2) = 22+32+32=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

题解

求所有满足 x=f(y,K)-y 的数量
计算一下,可以发现 y 最多为 10 位 (计算下极端情况)
而暴力搜索 10 位的数字显然会超时
可以采用 中途相遇法 的思路,将 10 位数字分成两个 5 位
然后分别计算两部分,再对两部分进行比较即可

首先可以知道, f(y,K) 函数是一个有确定的函数,因此可以打表直接查询结果
而每次需要求的 zK 也是有确切结果的,也可以打表(对于这道题,不打表时间会多很多)

将 x=f(y,K)-y 化成 x=f(a,K)+f(b,K)-a*100000-b 其中 a b 分别是 y 的前 5 位和后 5 位
可以看出, f(a,K)-a*100000 和 f(b,K)-b 可以分别在自己的循环里计算

用一个数组来记录第一个循环能得到的结果,在第二个循环里累计其结果在第一个循环里的数量
(用 map 会超时,可以用 lower_bound() 和 upper_bound() 快速求个数)

特别注意,如果 x=0 在两个循环会被重复计算 1 次,因此要额外 -1

代码量不大,思路也比较容易理解,注意各种打表优化即可

代码

//#include <ctime>
//#define debug

#include <cstdio>
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <cstring>

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 > 0) {
        half = size >> 1;
        mid = first + half;
        if (arr[mid] < 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 > 0) {
        half = size >> 1;
        mid = half + first;
        if (arr[mid] > 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("in.txt","r",stdin);
    int start = clock();
    #endif

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

    int T;
    cin >> T;
    //scanf("%d",&T);

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

    for(int i=0;i<100000;i++){
        for(int j=1;j<=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 <= T;kase++) {
        LL x;
        int k;
        cin >> x >> k;
        //scanf("%d%d",&x,&k);

        //前5位的各位k次方 - 前五位数据
        for(int i = 0;i < 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 < 100000;i++) {
            LL post = f(i,k) - (LL)i;
            LL pre = x - post;
            cnt += Count(pre);
        }
        cout << "Case #" << kase << ": " << cnt-(x==0) << endl;
       // printf("Case #%d: %d\n",kase,cnt);
    }

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

    return 0;
}