1600 - Lucky Numbers
时间限制：2秒 内存限制：64兆
401 次提交 109 次通过
题目描述
Isun loves digit 4 and 8 very much. He thinks a number is lucky only if the number satisfy the following conditions:
1. The number only consists of digit 4 and 8.
2. The number multiples 48.
One day, the math teacher gives Isun a problem:
Given L and R(1 <= L <= R <= 10^15), how many lucky numbers are there between L and R. (i.e. how many x satisfy L <= x <= R, x is a lucky number).
输入
Multiple test cases. For each test case, there is only one line consist two numbers L and R.
输出
For each test case, print the number of lucky numbers in one line.
Do use the %lld specifier or cin/ cout stream to read or write 64-bit integers in С++.
样例输入
1 48
1 484848
样例输出
1
7
提示
用深搜把每个符合条件的数字找出来，打表，然后就好了
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
using namespace std;
long long int l,r;
long long int ans[200005];
int cot;
int count(int x)
{
int num=0;
while(x>0)
{
num++;
x/=10;
}
return num;
}
void dfs(long long int x,int cnt)
{
if(cnt>16)
return;
if(x%48==0)
ans[cot++]=x;
dfs(x*10+8,cnt+1);
dfs(x*10+4,cnt+1);
}
int cmp(long long int x,long long int y)
{
return x<y;
}
int main()
{
cot=0;
memset(ans,0,sizeof(ans));
dfs(4,1);
dfs(8,1);
while(scanf("%lld%lld",&l,&r)!=EOF)
{
sort(ans,ans+cot,cmp);
int pos=0;
for(int i=0;i<cot;i++)
{
if(l<=ans[i])
{
pos=i;
break;
}
}
int res=0;
for(int i=pos;i<cot;i++)
{
if(ans[i]<=r)
res++;
else
break;
}
printf("%d
",res);
}
return 0;
}