数位dp #1
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std ;
typedef long long ll ;int a[20] ;
int dp[20][2] ;int dfs( int pos , int pre ,int sta , bool limit){if( pos <= -1) return 1 ;if( !limit && dp[pos][sta] != -1 ) return dp[pos][sta] ;int up = limit ? a[pos] : 9 ;int temp = 0 ;for( int i = 0 ; i <= up ; i ++ ){if( pre == 6 && i == 2) continue ;if( i == 4 ) continue ;temp += dfs(pos-1 , i , i==6 , limit && i==a[pos]);}if( !limit ) dp[pos][sta] = temp ;return temp ;
}int solve( int x ){int pos = 0 ;while( x ){a[pos ++] = x % 10 ;x /= 10 ;}int ans = dfs(pos - 1 , -1 , 0 , true ) ;return ans ;
}int main(){int n , m ;while( ~ scanf("%d %d",&n , &m) ){memset( dp , -1 , sizeof( dp )) ;if( !n && !m) break ;//for( int i = 0 ; i <= N ; i ++ ) G[i].clear() ;//memset( centroid , 0 , sizeof( centroid )) , memset(subtree_size , 0 , sizeof(subtree_size)) ;printf("%d\n" , solve(m) - solve(n-1));}return 0 ;}