题目思路：
dp[][0]存放不含不吉利数字的个数
dp[][1]存放上一位为6且不含不吉利数字的个数
dp[][2]存放含不吉利数字的个数
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<vector> 5 #include<stdio.h> 6 #include<stdlib.h> 7 #include<queue> 8 #include<math.h> 9 #include<map> 10 #define INF 0x3f3f3f3f 11 #define MAX 1000005 12 #define Temp 1000000000 13 14 using namespace std; 15 16 long long dp[20][3]; 17 int num[20]; 18 19 long long dfs(int pos,int status,int limit) 20 { 21 if(pos<0) 22 return status==2;//若含不吉利数字计数器加1 23 if(!limit && dp[pos][status]!=-1) 24 return dp[pos][status]; 25 long long ans=0; 26 int len=limit?num[pos]:9; 27 for(int i=0;i<=len;i++) 28 { 29 if(i==4 || status==2 || (i==2 && status==1)) 30 ans+=dfs(pos-1,2,i==len&&limit); 31 else if(i==6) 32 ans+=dfs(pos-1,1,i==len&&limit); 33 else 34 ans+=dfs(pos-1,0,i==len&&limit); 35 } 36 if(!limit) 37 dp[pos][status]=ans; 38 return ans; 39 } 40 41 long long solve(long long a) 42 { 43 int len=0; 44 memset(num,-1,sizeof(num)); 45 memset(dp,-1,sizeof(dp)); 46 while(a) 47 { 48 num[len++]=a%10; 49 a/=10; 50 } 51 return dfs(len-1,0,1); 52 } 53 54 int main() 55 { 56 long long a,b; 57 while(scanf("%lld%lld",&a,&b),a+b) 58 { 59 long long ans=solve(b)-solve(a-1); 60 printf("%I64d ",b-a+1-ans); 61 } 62 return 0; 63 }