Difference

　

difference

题目链接

---

题意

定义 $f(y,k)$f(y,k) 为 $y$y 各个数位上数字的 $k$k 次方和，问有多少个不同的 $y$y 满足 $x=f(y,k)-y$x=f(y,k)−y

---

分析

每个数位上的数字最大为9，假设 $y$y 由 $a$a 位9构成，那么 $x=a\ast 9^k-(10^a-1)$x=a∗9k−(10a−1) ，$k$k 最大为9，$x$x 最大为 $10^9$109，根据上式，$y$y 最多10位

令 $y=a\ast 10^5+b$y=a∗105+b，那么有 $x=f(a,k)+f(b,k)-a\ast 10^5-b$x=f(a,k)+f(b,k)−a∗105−b，可得 $x-f(a,k)+a\ast 10^5=f(b,k)-b$x−f(a,k)+a∗105=f(b,k)−b

预处理$f(b,k)-b$f(b,k)−b，枚举 $a$a，二分查找满足条件的 $b$b 的数量

$a,b$a,b最多各5位，时间复杂度为$O(5e5\cdot lo{g}_{2}10)$O(5e5⋅log2​10)

题目要求 $y$y 为正整数，特判0

---

代码

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#include<time.h>
#include<iOStream>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>

using namespace std;

#define bll long long

const int maxn = 1e5+100;
const int num = 1e5;
bll f[10][maxn],pre[10][maxn];
int fac[10][10];

void init()
{
    for (int i=1;i<10;i++)
    {
        fac[i][0] = 1;
        for (int j=1;j<10;j++) fac[i][j] = fac[i][j-1]*i;
    }

    for (int i=0;i<1e5;i++)
    {
        for (int k=1;k<10;k++)
        {
            int x = i;
            while (x)
            {
                f[k][i] += fac[x%10][k];
                x = x/10;
            }
            pre[k][i] = f[k][i]-i;
        } 
    }
    
    for (int i=1;i<10;i++) sort(pre[i],pre[i]+num);
    return;
}

long long solve(bll *p,bll *F,int x)
{
    long long ans = 0;
    for (int i=0;i<1e5;i++)
    {
        long long tmp = (bll)i*1e5-F[i]+x;
        ans += upper_bound(p,p+num,tmp)-lower_bound(p,p+num,tmp); 
    }
    return ans-(x==0);
}

int main()
{
    init();

    int T,k,x;
    scanf("%d",&T);
    for (int Case = 1; Case <= T; Case++)
    {
        scanf("%d %d",&x,&k);
        printf("Case #%d: %lld\n",Case,solve(pre[k],f[k],x));
    }
    return 0;
}

相关阅读