幸運(yùn)數(shù)字
【題目描述】
在中國(guó)，很多人都把6和8視為是幸運(yùn)數(shù)字！lxhgww也這樣認(rèn)為，于是他定義自己的“幸運(yùn)號(hào)碼”是十進(jìn)制表示中只包含數(shù)字6和8的那些號(hào)碼，比如68，666，888都是“幸運(yùn)號(hào)碼”！但是這種“幸運(yùn)號(hào)碼”總是太少了，比如在[1,100]的區(qū)間內(nèi)就只有6個(gè)（6，8，66，68，86，88），于是他又定義了一種“近似幸運(yùn)號(hào)碼”。lxhgww規(guī)定，凡是“幸運(yùn)號(hào)碼”的倍數(shù)都是“近似幸運(yùn)號(hào)碼”，當(dāng)然，任何的“幸運(yùn)號(hào)碼”也都是“近似幸運(yùn)號(hào)碼”，比如12，16，666都是“近似幸運(yùn)號(hào)碼”。
現(xiàn)在lxhgww想知道在一段閉區(qū)間[a, b]內(nèi)，“近似幸運(yùn)號(hào)碼”的個(gè)數(shù)。
【輸入】
輸入數(shù)據(jù)是一行，包括2個(gè)數(shù)字a和b
【輸出】
輸出數(shù)據(jù)是一行，包括1個(gè)數(shù)字，表示在閉區(qū)間[a, b]內(nèi)“近似幸運(yùn)號(hào)碼”的個(gè)數(shù)
【樣例輸入1】
1 10
【樣例輸出1】
2
【樣例輸入2】
1234 4321
【樣例輸出2】
809
【數(shù)據(jù)范圍】
對(duì)于30%的數(shù)據(jù)，保證1<=a<=b<=1000000
對(duì)于100%的數(shù)據(jù)，保證1<=a<=b<=10000000000
//================================================================
用容斥原理做。
先造出所有的幸運(yùn)號(hào)碼，然后對(duì)幸運(yùn)號(hào)碼的倍數(shù)容斥。
幸運(yùn)號(hào)碼有2000+個(gè)，為了盡快出解，要加幾個(gè)剪枝：
1. 如果A是B的倍數(shù)，直接去掉。剪掉了一大半。。。
2.從大到小排序，盡快容斥掉一些數(shù)。
寫的常數(shù)稍微少點(diǎn)能進(jìn)2s了。。
PS ：關(guān)于中間結(jié)果會(huì)爆long long的問題。。。從正的爆成負(fù)的容易，從正的爆成負(fù)的再爆成正的不容易。。。所以猥瑣的判大于0。。。
1
#include <iostream>
2#include <algorithm>
3#define NNUM 3000
4#define ll long long
5
6using namespace std;
7
8ll A,B;
9
void Init()
{
10
scanf("%I64d%I64d",&A,&B);
11
}
12
13int n = 0;
14ll a[NNUM+1];
15void 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}
22int cnt = 0;
23ll b[NNUM+1];
24
25ll Ans = 0, tmp;
26inline ll gcd(ll a, ll b){
27 while (b)
28 tmp = a, a = b, b = tmp % b;
29 return a;
30}
31
32
33int cmp(const void *a, const void *b){
34 return (*(ll *)b) > (*(ll *)a) ? 1 : -1;
35}
36
37ll 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
46void 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
68int main(){
69 freopen("luckynumber.in","r",stdin);
70 freopen("luckynumber.out","w",stdout);
71 Init();
72 Solve();
73 return 0;
74}
75