311. 月之谜
题目描述
如果一个十进制数能够被它的各位数字之和整除,则称这个数为“月之数”。
给定整数 L 和 R,你需要计算闭区间 [L,R] 中有多少个“月之数”。
输入格式
输入占一行,包含两个整数 L 和 R。
输出格式
输出一个整数,表示月之数的个数。
数据范围
1≤L,R<231
输入样例:
1 100
输出样例:
33
思路:题目意思很简单,就是让统计一下[l,r]中能被各位数字之和整除的数(月之数)的个数。
因为数位dp可以统计出小于等于当前数n的所有数(1-n)中的满足条件的数的个数,记为solve(n),
所以可以利用数位dp+前缀和的思想,统计出solve(r)和solve(l-1),[l,r]中月之数的个数显然即为:
solve(r)−solve(l−1)solve(r)−solve(l−1)
在数位dp时,枚举每个数位,将其数位上的数字加起来以求出各位数字之和显然会超时,
所以对于每个数的各位数字之和只要暴力枚举一下即可(因为其上限较小),然后从高位到低位枚举时,依次保留一个当前数值除以各位数字之和的余数mod,最后递归到最后一位时,判断一下余数是否为0,即可得出当前数能否被其各位数字之和整除,也就是是不是月之数了。
注:用f[pos][sum][mod]表示当前位编号位pos,各位数字之和位sum且当前余数位mod时,月之数的个数。
每次枚举当前假设的各位数字之和p,在dfs之前,要将f数组初始化为-1
完整代码:
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
const int maxn=100;//maxn为数据中各位数字之和的上限
int f[30][maxn][maxn],num[maxn],p;
int dfs(int pos,int sum,int mod,bool limit)//pos为当前数位,sum为当前真实数位之和(p为枚举的数位之和),mod为当前余数,limit为上一位是否达到上限的标志
{
if(!pos){//pos从最到位枚举到了最低位0
if(sum==p&&!mod) return 1;//如果当前各位数字之和=本次枚举的各位数字之和且除到最后余数为0,则说明当前各位数字之和能整除当前数,则说明当前数为月之数,返回统计数量+1
return 0;
}
if(!limit&&f[pos][sum][mod]!=-1) return f[pos][sum][mod];
int res=0,up=limit?num[pos]:9;
for(int i=0;i<=up;i++){
res+=dfs(pos-1,sum+i,(mod*10+i)%p,limit&&i==up);
}
return limit?res:f[pos][sum][mod]=res;
}
int solve(int n)//计算1-n中满足条件的数(月之数)的个数
{
int cnt=0;
while(n){
num[++cnt]=n%10;
n/=10;
}
int res=0;
for(p=1;p<maxn;p++){//枚举当前数位之和
memset(f,-1,sizeof f);
res+=dfs(cnt,0,0,1);
}
return res;
}
signed main()
{
int l,r;
cin>>l>>r;
cout<<solve(r)-solve(l-1)<<endl;
return 0;
}
太强了
%%%
%%%厉害厉害
$$\Huge\color{MediumSpringGreen}{我}\color{Lime}{要}\color{LimeGreen}{鼠}\color{MediumAquaMarine}{了}$$