这题就是数位dp,这里不多解释了,传送门在此:
https://blog.csdn.net/qq_41090676/article/details/86821500
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
int digit[20];
long long dp[20][2];
ll dfs(int len,bool is6,bool limit)
{
if (len==0)
return 1;
if (!limit&&dp[len][is6])
return dp[len][is6];
ll cnt = 0, up_bound = (limit ? digit[len] : 9);
for (int i = 0; i <= up_bound;i++) {
if (is6&&i==2)
continue;
if (i==4)
continue;
cnt += dfs(len - 1, i == 6, limit && i == up_bound);
}
if (!limit)
dp[len][is6] = cnt;
return cnt;
}
ll solve(ll num)
{
int k = 0;
while (num) {
digit[++k] = num % 10;
num /= 10;
}
return dfs(k, false, true);
}
int main()
{
ll n, m;
while (cin>>n>>m&&n+m) {
memset(dp, 0, sizeof(dp));
cout << solve(m) - solve(n-1) << endl;
}
return 0;
}