对正整数-x设-fxB-表示-x-在-B-进制下的数位和。说一个正整数-p-是-B-好的当且仅当对于任意正整数-qp都有-fpB=fqB。nn给定正整数-n-和-B计算有多少个-=n-的正整数是-B-好的。nn输入格式n本题单个测试点内有多组数据。nn第一行是数据组数-T。nn接下来-T-行每行两个正整数-nB。nn输出格式n输出-T-行每行一个非负整数为答案。nn写出c++代码

#include <iostream>
#include <cstring>
using namespace std;

typedef long long LL;

const int N = 20;

int n, b;
LL f[N][N * 9 + 1][2];

LL dfs(int pos, int sum, int limit)
{
    if (pos == -1) return sum;

    if (f[pos][sum][limit] != -1 && !limit) return f[pos][sum][limit];

    LL res = 0;
    int up = limit ? (n >> pos & 1) : b - 1;
    for (int i = 0; i <= up; i ++ )
        res += dfs(pos - 1, sum + i, limit && i == up);

    if (!limit) f[pos][sum][limit] = res;
    return res;
}

LL dp(LL x)
{
    // 将 x 转化为 b 进制
    int k = 0;
    LL temp = x;
    while (temp)
    {
        k ++ ;
        temp /= b;
    }
    temp = x;
    int c[k];
    memset(c, 0, sizeof c);
    for (int i = k - 1; i >= 0; i -- )
    {
        c[i] = temp % b;
        temp /= b;
    }

    // 计算 <= x 的数中的 B-好数个数
    LL res = 0;
    int sum = 0;
    for (int i = k - 1; i >= 0; i -- )
    {
        for (int j = (i == k - 1); j < c[i]; j ++ )
            res += dfs(i - 1, sum + j, 0);
        sum += c[i];
    }
    if (sum >= f[k - 1][0][0]) res ++ ;

    return res;
}

int main()
{
    int T;
    cin >> T;
    memset(f, -1, sizeof f);
    while (T -- )
    {
        cin >> n >> b;
        cout << dp(n) << endl;
    }

    return 0;
}

思路分析

本题是一道比较难的数位 DP 题目。

首先我们需要知道什么是 B-好数。对于一个正整数 p，它在 B 进制下的数位和为 $f(p, B)$，那么 p 是 B-好数当且仅当对于任意正整数 q < p，都有 $f(p,B) \ge f(q,B)$。

然后我们需要求出 <=n 的 B-好数个数。这个问题可以通过数位 DP 解决。我们可以枚举从高到低的每一位，计算出满足该位及其以下位的数中，B-好数的个数。最后统计答案即可。

具体来说，我们可以使用 dfs(pos, sum, limit) 表示当前考虑到二进制下第 pos 位，前面的数位和为 sum，当前位是否达到上界的状态。其中 limit=0 表示当前位还没有到达上界，limit=1 表示当前位已经到达上界。

对于每一位，我们枚举该位的取值，然后递归计算下一位的方案数。注意当 limit=0 时，需要将当前状态的结果记录下来，避免重复计算。

最后，我们可以将 n 转化为 B 进制，然后从高到低枚举每一位，计算满足该位及以下位的数中，B-好数的个数。注意如果当前数的数位和大于等于上限，那么这个数一定是 B-好数。