链接：https://ac.nowcoder.com/acm/contest/329/G
来源：牛客网
题目描述
经过了选号和漫长的等待，处女座终于拿到了给小姐姐定制的手环，小姐姐看到以后直呼666！
处女座其实也挺喜欢6这个数字的，实际上他做手环的时候选取的k=6。所以他对于包含数码6的数字极其敏感。每次看到像4567这样的数字的时候他的心就像触电了一样，想起了小姐姐。
现在你要给处女座展示一系列数字，你想知道他的内心会激动多少次。对于同一个数字，他最多只会激动一次，即如果这个数是66666，他还是只会激动一次。
输入描述:
一行包括两个数字l,r，表示你给处女座展示的数字范围为[l,r]。
输出描述:
一行一个整数，表示处女座内心激动的次数。
示例1
输入
10 20
输出
1
备注:
0≤l≤r≤1018
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<math.h>
#include<vector>
#include<queue>
#include<map>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
ll dp[][];///dp[i][j]表示i+1位数，且以j为开头，不包含6的数的个数
void init()
{
memset(dp,,sizeof(dp));
dp[][]=;
for(int i=;i<;i++)///i表示从右往左开始第几位，j表示第i位上的数字
{
for(int j=;j<;j++)
{
for(int k=;k<;k++)
if(j!=)///不累计第i位上数字为6的个数
dp[i][j] += dp[i-][k];
}
}
}
ll solve(ll x)//求 1到(x-1)里 不包含6的数 的个数
{
ll temp=x;
int num[];
int cnt=;
while(x)//记录各个位置上的数字
{
num[cnt++]=x%;
x=x/;
}
num[cnt]=;
ll res=;
for(int i=cnt-;i>;i--)///有多少位
{
for(int j=;j<num[i];j++)//如果该位上数字为0的话，是不满足累加要求的
{
// if(j!=6) //这一步可以不要的，因为dp[i][6]=0
res+=dp[i][j];
}
if(num[i]==)///比如3650，遇到6，后面直接不用算了
break;
}
return temp-res;//返回不包含6的数字的个数
} int main()
{
init();
ll l,r;
while( scanf("%lld%lld",&l,&r)!=EOF )
{
ll ans;
ans=solve(r+)-solve(l);
printf("%lld\n",ans);
}
return ;
}