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

Mier_Samuelle · 2025-05-02 17:27:13 · 题解

场切了。

Statement

我们定义：

给定 k，t 次询问，每次给定 m，求 y=f_k(x) 与 y=m 的图象的公共点个数。

数据范围：1 \le t \le 10^5，0 \le k \le 10^9，1 \le m \le 10^{18}。

Analysis

根据 Subtask 提示，分几种情况考虑：

• 当 k=0 时：
  • 由题意知 f_0(x)=x=m。
  • 答案显然为 1。
• 当 k=1 时：
  • 由题意知 f_1(x)=x+s(x)=m。
  • 由于 x 可能很大，枚举 x 无法接受，故考虑枚举较小的 s(x)。
  • 具体地，枚举 a \in [1,162]，则 x=m-a。
  • 验证 s(x)=a 是否成立即可。
• 当 k=2 时：
  • 由题意知 f_2(x)=x+s(x)+s(s(x))=m。
  • 类似地，枚举 a \in [1,162]，记 b=s(a)，则 x=m-a-b。
  • 验证 s(x)=a 且 s(s(x))=b 是否成立即可。
• 当 k \ge 3 时：
  • 由题意知 f_k(x)=x+s(x)+s(s(x))+\dots+S_k(x)=m。
  • 注意到，当 k 逐渐增大时，S_k(x) 减小极快。
  • 实际上，对于任意 x \le m \le 10^{18}，当 k \ge 3 时，S_k(x) 都是相同的。
  • 因此，枚举 a \in [1,162]，记 b=s(a)，c=s(b)，则 x=m-a-b-(k-2) \times c。
  • 验证 s(x)=a，s(s(x))=b 且 s(s(s(x)))=c 是否成立即可。

复杂度是常数级的。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 0x3f3f3f3f3f3f3f3f;
int t, k;
int s(int x){
    int ret = 0;
    while (x > 0){
        ret += x % 10;
        x /= 10;
    }
    return ret;
}
void solve(){
    int m;
    cin >> m;
    int cnt = 0;
    if (k == 0){ //不要忘记 k=0 的情况
        cout << 1 << endl;
        return;
    }
    for (int a = 0;a <= 200;a++){
        int b = s(a), c = s(b), d = s(c);
        if (k == 1){
            int x = m - a;
            cnt += (s(x) == a);
        }
        else if (k == 2){
            int x = m - a - b;
            cnt += (s(x) == a && s(s(x)) == b);
        }
        else{
            int x = m - a - b - c * (k - 2);
            cnt += (s(x) == a && s(s(x)) == b && s(s(s(x))) == c);
        }
    }
    cout << cnt << endl;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> t >> k;
    while (t--) solve();
    return 0;
}