#include<bits/stdc++.h> using namespace std; typedef long long ll; #define fi first #define se second ll f(ll n){ ll prod=1; while(n){ prod*=n%10; n/=10; } return prod; } ll ff(ll n){ if(n<10) return n; return ff(f(n)); } int sz; unordered_map<ll,int>mp; ll val[50005]; int tr[50005][10]; int res[50005]; const int iu=18; int osz[50005];// ll dp[20][50005];//distribution of f [0..9]^k ll ep[20][50005];//distribution of f [1..9][0..9]^(p) for some 0<=p<k void pre(){ sz=1; mp[1]=1; val[1]=1; osz[0]=1; dp[0][1]=1; int sex=0; for(int r=1; r<=iu ;r++){ for(int j=1; j<=osz[r-1] ;j++){ ep[r][j]+=ep[r-1][j]; for(int k=0; k<10 ;k++){ if(tr[j][k]==0){ ll newi=val[j]*k; if(newi%10==0) newi=0; if(mp[newi]==0){ mp[newi]=++sz; val[sz]=val[j]*k; } tr[j][k]=mp[newi]; } dp[r][tr[j][k]]+=dp[r-1][j]; if(k!=0) ep[r][tr[j][k]]+=dp[r-1][j]; } } osz[r]=sz; sex+=sz; } //cout << sex << endl; for(int i=1; i<=sz ;i++) res[i]=ff(val[i]); } ll ans[10]; void solve(){ ll n;//cin >> n; //n=1e18;n-=rand(); cin >> n; for(int i=0; i<10 ;i++) ans[i]=0; if(n==1e18){ ans[0]++; --n; } ans[ff(n)]++; for(int s=0; n>0 ;s++,n/=10){//n%10 is the first digit m < n int st=1; ll pre=1; if(n>=10){ st=0; pre=f(n/10); } //pre+[st,n%10)+ [0..9]^s for(int j=1; j<=osz[s] ;++j){ ll curr=mp[val[j]*pre]; for(int k=st; k<n%10 ;k++){ ll cur=tr[curr][k]; ans[res[cur]]+=dp[s][j]; } } if(st==1){//len shorter than for(int j=1; j<=osz[s] ;++j) ans[res[j]]+=ep[s][j]; } } for(int i=0; i<10 ;i++) cout << ans[i] << ' '; cout << '\n'; } int main(){ ios::sync_with_stdio(false);cin.tie(0); pre(); int t;cin >> t;while(t--) solve(); }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 | #include<bits/stdc++.h> using namespace std; typedef long long ll; #define fi first #define se second ll f(ll n){ ll prod=1; while(n){ prod*=n%10; n/=10; } return prod; } ll ff(ll n){ if(n<10) return n; return ff(f(n)); } int sz; unordered_map<ll,int>mp; ll val[50005]; int tr[50005][10]; int res[50005]; const int iu=18; int osz[50005];// ll dp[20][50005];//distribution of f [0..9]^k ll ep[20][50005];//distribution of f [1..9][0..9]^(p) for some 0<=p<k void pre(){ sz=1; mp[1]=1; val[1]=1; osz[0]=1; dp[0][1]=1; int sex=0; for(int r=1; r<=iu ;r++){ for(int j=1; j<=osz[r-1] ;j++){ ep[r][j]+=ep[r-1][j]; for(int k=0; k<10 ;k++){ if(tr[j][k]==0){ ll newi=val[j]*k; if(newi%10==0) newi=0; if(mp[newi]==0){ mp[newi]=++sz; val[sz]=val[j]*k; } tr[j][k]=mp[newi]; } dp[r][tr[j][k]]+=dp[r-1][j]; if(k!=0) ep[r][tr[j][k]]+=dp[r-1][j]; } } osz[r]=sz; sex+=sz; } //cout << sex << endl; for(int i=1; i<=sz ;i++) res[i]=ff(val[i]); } ll ans[10]; void solve(){ ll n;//cin >> n; //n=1e18;n-=rand(); cin >> n; for(int i=0; i<10 ;i++) ans[i]=0; if(n==1e18){ ans[0]++; --n; } ans[ff(n)]++; for(int s=0; n>0 ;s++,n/=10){//n%10 is the first digit m < n int st=1; ll pre=1; if(n>=10){ st=0; pre=f(n/10); } //pre+[st,n%10)+ [0..9]^s for(int j=1; j<=osz[s] ;++j){ ll curr=mp[val[j]*pre]; for(int k=st; k<n%10 ;k++){ ll cur=tr[curr][k]; ans[res[cur]]+=dp[s][j]; } } if(st==1){//len shorter than for(int j=1; j<=osz[s] ;++j) ans[res[j]]+=ep[s][j]; } } for(int i=0; i<10 ;i++) cout << ans[i] << ' '; cout << '\n'; } int main(){ ios::sync_with_stdio(false);cin.tie(0); pre(); int t;cin >> t;while(t--) solve(); } |