Description
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).
Input
Multiple test cases. For each test case, there is only one line consist two numbers L and R.
Output
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 С++.
Sample Input
1 48 1 484848
Sample Output
1
7
直接预处理出全部的lucky number，然后每次询问可以直接二分找到区间，相减就是答案。
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<iostream>
#include<queue>
#include<map>
#include<bitset>
#include<algorithm>
using namespace std;
typedef long long LL;
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int maxn = 3e5 + 10;
LL l, r;
LL a[maxn], tot;
void dfs(int x, LL y)
{
if (x == 15) return;
if (y % 48 == 0) a[tot++] = y;
dfs(x + 1, y * 10 + 4);
dfs(x + 1, y * 10 + 8);
}
int main()
{
tot = 0; dfs(0, 0); sort(a, a + tot);
while (scanf("%lld%lld", &l, &r) != EOF)
{
int x = lower_bound(a, a + tot, l) - a;
int y = upper_bound(a, a + tot, r) - a;
printf("%d\n", y - x);
}
return 0;
}