数位dp
dp[i][j] 表示最高位数为i，最高位为j 的无限制选择个数和。 注意“无限制”。
使用记忆化搜索。记录是否限制 和 前面是否为0. ！！这里很重要！！！
#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<cstring>using namespace std;typedef long long ll;const int N = 10+10;ll dp[N][N];//dp[i][j] 为第i位为j的无限制个数ll dig[N];ll dfs(int len,int pre,int f,int z)// f 当前数位的选择是否限制， Z 前面的数是否都为0{if(len < 1) return 1;if(z==0 && !f && dp[len][pre]!=-1) return dp[len][pre];ll res = 0;int last = f ? dig[len] : 9;for(int i=0;i<=last;i++){if(z==0 || ( pre>=i && i!=0 && pre%i==0 ) )res += dfs(len-1,i,f&&(i==last),z||i);}if(!f && z==0) dp[len][pre] = res;return res;}int solve(int num){int len = 0;while(num){dig[++len] = num % 10;num /= 10;}return dfs(len,0,1,0);}int main(){int t,l,r;cin>>t;memset(dp,-1,sizeof(dp));while(t–){scanf("%d%d",&l,&r);ll ans = solve(r) – solve(l-1);printf("%lld\n",ans);}return 0;}
，你在雨中行走，你从不打伞，你有自己的天空，它从不下雨。
