https://nanti.jisuanke.com/t/41422

题意：直接看图，简单明了

分析：

这个我觉得有必要从时间复杂度层面分析这道题目。首先如果是无脑采取暴力的做法，时间复杂度是O(1e5*1e6),必然超时，做都不用做，肯定要换算法或者优化。我们可以观察到本题有T（100000）种case，如果我们每次case都要对N这么大的范围进行暴力操作查找，那么肯定是会超时的，所以我们可以在进入case前进行预处理，这是程序设计经常会使用的方法，当我们对大数据预处理后，查找的时间复杂度就会变成O（1）。可以计算，预处理的部分代码并不会超时。然后，本题的具体操作较为简单，罪犯的超时问题可以预处理解决。但是如果数据N再大一点呢？预处理都会超时，有没有更好的方法？待想。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6;
ll ans[11][N+1];

ll fen(int a,int b)
{
    ll sum=0;
    while(a)
    {
        sum+=a%b;
        a=a/b;
    }
    return sum;
}
int main()
{
    int T,x,y;
    scanf("%d",&T);
    for(int i=2;i<=10;i++) ans[i][1]=1;
    for(int i=2;i<=10;i++)
    {
        for(int j=2;j<=1000000;j++)
        {
            ans[i][j]=ans[i][j-1]+fen(j,i);
        }
    }
    int k=1;
    for(int i=1;i<=T;++i)
    {
        scanf("%d%d",&x,&y);
        printf("Case #%d: %lld\n",k++,ans[y][x]);
    }
}