题解：P12397 「FAOI-R9」函数大师

题目大意

给定一个正整数函数：

• 表示 的十进制数字之和；
• ，；
• 。

对于固定的 ，有 个查询，每次给定 ，求满足 的正整数 的个数。

函数分析

1. 数字和上界：对于 ，.
2. 数根 ：
   • ；
   • ，且对任意 ，（数根）。

由此， 至多包含如下四种项：

• ；
• ；
• ；
• 对于 ，还要加上 个 ，即 。

分类讨论

记 ，。

情况 1：

只要 ，唯一解 ，答案为 1，否则为 0。

情况 2：

枚举 ，令 ，检查 且 即可。

情况 3：

枚举 ，令

检查 且 即可。

情况 4：

枚举：

1. 数根 ；

2. 数字和 ；

3. 令
   
   并校验 。

每次枚举 的步长为 9，总共 次，共 次检查。

时间复杂度

对每个查询最多做 次常数级检查， 时总计 次，C++ 可在 1s 内完成。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll T, k, m;

inline ll read() {
    ll x = 0;
    char ch = getchar();
    while (!isdigit(ch))
        ch = getchar();
    while (isdigit(ch)) {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x;
}

inline int digitSum(ll x) {
    int s = 0;
    while (x)
        s += x % 10, x /= 10;
    return s;
}
int digitalRoot(ll x) {
    return digitSum(digitSum(digitSum(x)));
}

inline ll k0() {
    return (m >= 1 ? 1 : 0);
}
inline ll k1() {
    ll res = 0;
    for (int t = 1; t <= 171 && t < m; t++)
        if (digitSum(m - t) == t)
            res++;
    return res;
}
inline ll k2() {
    ll res = 0;
    for (int t = 1; t <= 171; t++) {
        ll x = m - t - digitSum(t);
        if (x >= 1 && digitSum(x) == t)
            res++;
    }
    return res;
}
inline ll k3() {
    ll res = 0;
    for (int d = 1; d <= 9; d++) {
        ll base = m - (k - 2LL) * d;
        for (int t = d; t <= 171; t += 9) {
            ll x = base - t - digitSum(t);
            if (x < 1)
                break;
            if (digitSum(x) == t && digitalRoot(x) == d)
                res++;
        }
    }
    return res;
}

int main() {
    T = read(), k = read();
    while (T--) {
        m = read();
        if (k == 0)
            cout << k0() << '\n';
        else if (k == 1)
            cout << k1() << '\n';
        else if (k == 2)
            cout << k2() << '\n';
        else
            cout << k3() << '\n';
    }
    return 0;
}