题目：给定一个区间的两个区间端点l和r，问在l和r之间有多少满足下列情况的数字—这个数字应该满足前一位是后一位的倍数。
分析：这是一个经典的数位DP的题目，我们可以把区间求和转化成两个区间的减法，即S[1,r]-S[1,l-1]就是我们求得的答案。
那么问题就转化成了求1-n之间满足情况的数的个数，那么我们就要使用dp[i][j]求得数字长度为i，首数字为j的满足情况的数的个数，然后累加进行预处理（具体见代码）。
随后分为以下几种情况讨论：1.比数字n位数少的，直接累加sum[i](为长度为i的所有满足情况的数的和，，即dp[i][j]（j>=1&&j<=9）的和)就可以了。
2.与数字n位数相同，但首数字比n的首数字小的，直接加上dp[n的长度][j](j>=1&&j<n的首字母)
3.与数字n位数相同，且首数字也相同的，使用dfs求解即可。
#include <iostream>#include <cstdio>#include <cmath>#include <cstring>using namespace std;int Sum[10],dp[10][10];void init(){memset(Sum,0,sizeof(Sum));memset(dp,0,sizeof(dp));for(int i=1;i<=9;i++){dp[1][i]=1;}for(int i=2;i<=9;i++){for(int j=1;j<=9;j++)for(int k=1;k<=j;k++)if(j%k==0){dp[i][j]+=dp[i-1][k];}}for(int i=1;i<=9;i++){for(int j=1;j<=9;j++)Sum[i]+=dp[i][j];//printf("%d\n",Sum[i]);}}int dfs(int nm,int st,int len,int dit[]){if(nm>dit[st]) return 0;if(nm<dit[st]) return dp[len-st][nm];if(nm==dit[st]){if(st==len-1) return 1;int ans=0;for(int i=nm;i>=1;i–)if(nm%i==0)ans+=dfs(i,st+1,len,dit);return ans;}}int Cal(int n){if(n<=9) return n;int dit[10];int len=log10(n)+1;//cout<<n<<":"<<len<<endl;int ans=0;for(int i=1;i<len;i++){ans+=Sum[i];}//cout<<"位数少的ans:"<<ans<<endl;for(int i=len-1;i>=0;i–){dit[i]=n%10;n/=10;}//cout<<"dit0:"<<dit[0]<<endl;for(int i=1;i<dit[0];i++){ans+=dp[len][i];}//cout<<"同位数小于dit0的ans:"<<ans<<endl;for(int i=dit[0];i>=1;i–)if(dit[0]%i==0)ans+=dfs(i,1,len,dit);//cout<<"Sum-ans:"<<ans<<endl;return ans;}int main(){init();//int dit[10];int l=0,r=0,num;/*for(int i=1;i<=20;i++){cout<<i<<":";num=i;l=Cal(num);int len=log10(num);for(int j=len;j>=0;j–){dit[j]=num%10;num/=10;}int flag=1;for(int j=0;j<len;j++)if(dit[j+1]==0||dit[j]%dit[j+1]){flag=0;break;}r+=flag;printf("%d %d\n",l,r);if(l!=r){printf("ERROR!\n");break;}}*/scanf("%d",&num);while(num–){scanf("%d%d",&l,&r);if(l>=1e9) l–;if(r>=1e9) r–;l–;l=Cal(l);r=Cal(r);//cout<<l<<" "<<r<<endl;printf("%d\n",r-l);}return 0;}
自己战胜自己是最可贵的胜利。
