幸运数字
【题目描述】
在中国,很多人都把6和8视为是幸运数字!lxhgww也这样认为,于是他定义自己的“幸运号码”是十进制表示中只包含数字6和8的那些号码,比如68,666,888都是“幸运号码”!但是这种“幸运号码”总是太少了,比如在[1,100]的区间内就只有6个(6,8,66,68,86,88),于是他又定义了一种“近似幸运号码”。lxhgww规定,凡是“幸运号码”的倍数都是“近似幸运号码”,当然,任何的“幸运号码”也都是“近似幸运号码”,比如12,16,666都是“近似幸运号码”。
现在lxhgww想知道在一段闭区间[a, b]内,“近似幸运号码”的个数。
【输入】
输入数据是一行,包括2个数字a和b
【输出】
输出数据是一行,包括1个数字,表示在闭区间[a, b]内“近似幸运号码”的个数
【样例输入1】
1 10
【样例输出1】
2
【样例输入2】
1234 4321
【样例输出2】
809
【数据范围】
对于30%的数据,保证1<=a<=b<=1000000
对于100%的数据,保证1<=a<=b<=10000000000
//================================================================
用容斥原理做。
先造出所有的幸运号码,然后对幸运号码的倍数容斥。
幸运号码有2000+个,为了尽快出解,要加几个剪枝:
1. 如果A是B的倍数,直接去掉。剪掉了一大半。。。
2.从大到小排序,尽快容斥掉一些数。
写的常数稍微少点能进2s了。。
PS :关于中间结果会爆long long的问题。。。从正的爆成负的容易,从正的爆成负的再爆成正的不容易。。。所以猥琐的判大于0。。。
1
#include <iostream>
2
#include <algorithm>
3
#define NNUM 3000
4
#define ll long long
5
6
using namespace std;
7
8
ll A,B;
9
void Init()
{
10
scanf("%I64d%I64d",&A,&B);
11
}
12
13
int n = 0;
14
ll a[NNUM+1];
15
void dfsNum(ll num)
{
16
if (num > B) return;
17
if (num <= B)
18
a[++n] = num;
19
dfsNum(num * (ll)10 + (ll)6);
20
dfsNum(num * (ll)10 + (ll)8);
21
}
22
int cnt = 0;
23
ll b[NNUM+1];
24
25
ll Ans = 0, tmp;
26
inline ll gcd(ll a, ll b)
{
27
while (b)
28
tmp = a, a = b, b = tmp % b;
29
return a;
30
}
31
32
33
int cmp(const void *a, const void *b)
{
34
return (*(ll *)b) > (*(ll *)a) ? 1 : -1;
35
}
36
37
ll dfs(int pos, ll num)
{
38
if (pos == n+1) return B/num - A/num;
39
ll ret = dfs(pos+1, num);
40
ll newnum = num / gcd(num, a[pos]) * a[pos];
41
if (newnum <= B && newnum >= 1)
42
ret -= dfs(pos+1, newnum);
43
return ret;
44
}
45
46
void Solve()
{
47
dfsNum(6); dfsNum(8);
48
qsort(a+1, n, sizeof(a[0]), cmp);
49
//printf("%d\n",n);
50
for (int i = 1; i<=n; i++)
{
51
bool boo = true;
52
for (int j = 1; j<=n; j++)
53
if (i!=j && a[i] % a[j] == 0)
{
54
boo = false;
55
break;
56
}
57
if (boo)
{
58
a[++cnt] = a[i];
59
//printf("%d %I64d\n", cnt, a[cnt]);
60
}
61
}
62
n = cnt;
63
//printf("%d\n",n);
64
A--;
65
printf("%I64d\n", B - A - dfs(1,1));
66
}
67
68
int main()
{
69
freopen("luckynumber.in","r",stdin);
70
freopen("luckynumber.out","w",stdout);
71
Init();
72
Solve();
73
return 0;
74
}
75