题解归档 - cf932B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf932B
• 本地来源：problems/cf932B/idea.md
• 题目链接：https://codeforces.com/contest/932/problem/B
• 原始标题：cf932B Recursive Queries

思路

cf932B Recursive Queries

题意

定义正整数上的函数：

• f(n)：若 n < 10 则 f(n)=n；否则 f(n) 为 n 各位非零数字之积。
• g(n)：若 n < 10 则 g(n)=n；否则 g(n)=g(f(n))。

共 Q 组询问，每组给 l,r,k，求 x∈[l,r] 中满足 g(x)=k 的个数。

做法

f(n)<n（n≥10），故 g 可自底向上递推。预处理 1..10^6 的 g(i)，再对 k=1..9 建前缀和 cnt[k][i]。每次询问 O(1)：cnt[k][r]-cnt[k][l-1]。

验证

样例与 stress.py -n 500 对拍通过。

代码

来源：problems/cf932B/solution.cpp

/* Author: likely
 * Time: 2026-06-08 05:22:29
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define maxn 1000005
ll g[maxn],s[10][maxn];
ll fpd(ll x){
    ll zc=1;
    while(x){
        if(x%10) zc*=(x%10);
        x/=10;
    }
    return zc;
}
int main(){
    ll t,n,i,j,k,l,r,zc,cnt,ans;
    for(i=1;i<maxn;i++){
        if(i<10) g[i]=i;
        else g[i]=g[fpd(i)];
    }
    for(i=1;i<maxn;i++){
        for(j=1;j<=9;j++) s[j][i]=s[j][i-1];
        if(g[i]>=1 and g[i]<=9) s[g[i]][i]++;
    }
    cin>>t;
    while(t--){
        cin>>l>>r>>k;
        cout<<s[k][r]-s[k][l-1]<<"\n";
    }
    return 0;
}