题意

求出区间 \([L,R]\) 中各位数字之和能整除原数的数的个数。

分析

整除的问题比较难处理。而整除的问题,我们只要数位和确定,就只需要看对数位和取模的结果,所以我们枚举数位和,考虑在这个数位和下在区间内数的个数。

用 \(f[i][j][k][m]\) 表示已经处理到第 \(i\) 位,剩下的位上数位和为 \(j\) , 对枚举的整个数的数位和取模的结果为 \(k\) , \(m=0/1\) 前 \(i\) 位是否于上限一致。

同样差分,特判下限即可。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注