给出两个数a,ba,b,求出\([a,b]\)中各位数字之和能整除原数的数的个数。
我们按照模板的做法来想,枚举到第pos位时,要确定这一位的数字,可以更新现在所填数字的和,但对于最终的和无从得知,是否能整除也无从判别,我们试着先确定了最终的和,在枚举每一位的时候注意到,枚举x,则对最终和模数可以更新为 \((mod * 10 + x) \% sum\) ,所以可以想到每一次枚举一个和sum
\(d[i][j][k]\)表示 i 位数字,前面填过的数字和为 j 时,模sum为 k 的数字个数
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll d[20][160][160],L,R;
int k[20],pos,mod;
//sum为之前填过的数字的和,p为之后要填的数字对mod的模为p
ll dfs(int pos,int sum,int p,bool lead,bool limit){if(pos == -1){if(p == 0 && sum == mod)return 1;else return 0;}if(!limit && !lead && d[pos][sum][p] != -1)return d[pos][sum][p];int up = limit ? k[pos] : 9;ll res = 0;for(int i = 0;i <= up;i ++){if(lead){if(i == 0){res += dfs(pos - 1, sum + i, p, true, false);}else {res += dfs(pos - 1, sum + i, (p * 10 + i) % mod, false, limit && i == k[pos]);}}else {res += dfs(pos - 1,sum + i, (p * 10 + i) % mod, false, limit && i == k[pos]);}}if(!limit && !lead) d[pos][sum][p] = res;return res;
}ll solve(ll x){pos = 0;while(x){k[pos++] = x % 10;x/=10;}ll res = 0;//mod为当前枚举的和for(mod=1;mod <= pos * 9;mod++){memset(d,-1,sizeof d);res += dfs(pos-1,0,0,true,true);}return res;
}
int main(){scanf("%lld%lld",&L,&R);//cout<<solve(R)<<' ' <<solve(L-1)<<endl;printf("%lld\n",solve(R)-solve(L-1));return 0;
}