给两个函数,g(x)和f(x) f(n)是求所有非零数位的积. 题目给我们 n,l,r,k其中n表示测试数据有几行,l,r是一个区间,要求在l,r区间满足g(x)=k的x的个数有多少.
数据范围:
1 求出从1到106 的g(x)的值.这里我们先写出1到9的g(x)的值.剩下的只要求一次f(x)就可以在前面找到某个值等于f(x)了(因为位数之积会小于原本的数). 2 由于是要统计一个区间的某个k值的个数. 直接遍历会超时,这里先打个表.统计前i个数中(1到9)有多少.然后前i+1就可以在这个基础上的某个值上加1就好了. 3求答案时ans[r][k]-ans[l-1][k]即可.
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <algorithm> #include <string.h> #include<cstring> #include <math.h> using namespace std; typedef long long ll; const ll maxn=1000100; ll gg[maxn]; ll ans[maxn][10]; ll f(ll x){ ll res=1; while(x!=0){ if(x%10!=0)res*=x%10; x=x/10; } return res; } int main() { for (ll i=0; i<10; i++){ gg[i]=i; } for (ll i=10; i<maxn; i++){ gg[i]=gg[f(i)]; } ans[1][1]=1; for(ll i =2; i<maxn; i++){ for(ll j=1; j<=9; j++){ if(gg[i]!=j)ans[i][j]=ans[i-1][j]; else ans[i][j]=ans[i-1][j]+1; } } ll n,l,r,k; cin>>n; for(ll i=0; i<n; i++){ cin>>l>>r>>k; cout<<ans[r][k]-ans[l-1][k]<<endl; } return 0; }