NC21755. little w and Digital Root
描述
数根(又称数字根Digital root)是正整数的一种性质，换句话说，每个正整数都有一个数根。 数根是将一正整数的各个位数相加(即横向相加)，若加完后的值大于等于10的话，则继续将各位数进行横向相加直到其值小于十为止，或是，将一数字重复做数字和，直到其值小于十为止，则所得的值为该数的数根。
比如：12345->15->6。
小w现在定义一种叫做小w数根运算，这种运算的规则如下： 首先对十进制数的每个数位定义了一个权值，个位为1，十位为2，百位为3，千位为4，万为为5......以此类推 接下来把这个数的各个位数乘以该数位的权值再相加求和，若加完后的值大于等于10的话，则重复此过程，直到整个数字小于10为止，所得的值为小w数根。 现在小w想知道给定一个值域[L,R](1<=L<=R<=1e18)，请你告诉他，值域范围内有多少个数字的小w数根等于1,2,3,4,5,6,7,8,9。
输入描述
第一行输入一个正整数T(T<=10^4)，表示样例的组数。对于每组案例： 输入两个正整数L,R(1<=L<=R<=1000000000000000000)
输出描述
对于每组案例，请先输出Case #x:，x表示当前样例编号。
然后在同一行输出9个整数，分别表示值域内小w数根等于1,2,3,4,5,6,7,8,9的数各有多少个。 整数之间用空格隔开，行末不允许有多余空格。
示例1
输入:
10 1 10 2 55 36 78 15 15 3 59 56 77 89 93 90 90 55 99 1 99
输出:
Case #1: 1 2 1 1 1 1 1 1 1 Case #2: 0 7 7 7 7 7 7 6 6 Case #3: 0 5 5 6 6 6 5 5 5 Case #4: 0 0 0 0 0 0 1 0 0 Case #5: 0 7 8 7 7 7 7 7 7 Case #6: 0 3 3 3 3 2 2 3 3 Case #7: 0 1 1 1 1 0 0 0 1 Case #8: 0 1 0 0 0 0 0 0 0 Case #9: 0 6 6 5 5 5 6 6 6 Case #10: 1 13 13 12 12 12 12 12 12
C++14(g++5.4) 解法, 执行用时: 112ms, 内存消耗: 29468K, 提交时间: 2020-09-01 15:17:09
#include<bits/stdc++.h>
using namespace std;
#define int long long
int j,a[66];
int dp[22][6666][2][12];
int vis[66];
int judge(int num){
if(num<10) return num;
while(1){
int sum=0;
int cnt=1;
while(num){
sum+=(num%10)*cnt++;num/=10;
}
if(sum<10) return sum;else num=sum;
}
}
int DP(int pos,int sum,int limit){
if(!pos) return j==judge(sum)?1:0;
if(!limit&&dp[pos][sum][limit][j]!=-1)
return dp[pos][sum][limit][j];
int high=limit?a[pos]:9;
int ans=0;
for(int i=0;i<=high;i++){
ans+=DP(pos-1,sum+i*pos,limit&&(i==high));
}
if(!limit)
dp[pos][sum][limit][j]=ans;
return ans;
}
int slove(int n){
int len=0;
while(n){
a[++len]=n%10;
n/=10;
}
return DP(len,0,1);
}
signed main(){
memset(dp,-1,sizeof(dp));
int T;
cin>>T;
int cnt=1;
while(T--){
int L,R;
scanf("%lld%lld",&L,&R);
printf("Case #%lld: ",cnt++);
for(j=1;j<=9;j++){
int res=slove(R)-slove(L-1);
if(j==1) printf("%lld",res);else printf(" %lld",res);
}
printf("\n");
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 131ms, 内存消耗: 5864K, 提交时间: 2018-12-24 22:53:39
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll t,l,r,a[12],nb,b[20],f[2010],dp[20][2010][12];
ll que(ll x,ll y,ll z,ll p){
if (!x)return f[z]==p;
if (y==0){if(dp[x][z][p]==-1){for(ll i=0;i<=9;i++)dp[x][z][p]+=que(x-1,0,z+x*i,p);dp[x][z][p]++;}return dp[x][z][p];}
ll s=0;
for (ll i=0;i<=b[x];i++)s+=que(x-1,i==b[x],z+x*i,p);
return s;
}
void add(ll x,ll y){nb=0;for(;x;x/=10)b[++nb]=x%10;for(int i=1;i<=9;i++)a[i]+=y*que(nb,1,0,i);}
ll que(ll x){ll s=0;for(ll i=1;x;x/=10,i++)s+=(x%10)*i;return s;}
int main(){
cin>>t;memset(dp,-1,sizeof(dp));
for (ll i=1;i<=2000;i++)f[i]=(i<=9)?i:f[que(i)];
for (ll i=1;i<=t;i++){
cin>>l>>r;add(r,1);add(l-1,-1);
cout<<"Case #"<<i<<":";
for (ll j=1;j<=9;j++){cout<<' '<<a[j];a[j]=0;}
puts("");
}
return 0;
}