Bzoj 1853: [Scoi2010]幸运数字容斥原理,深搜

1853: [Scoi2010]幸运数字

Time Limit: 2 Sec Memory Limit: 64 MB
Submit: 1774 Solved: 644
[Submit][Status][Discuss]

Description

在中国，很多人都把6和8视为是幸运数字！lxhgww也这样认为，于是他定义自己的“幸运号码”是十进制表示中只包含数字6和8的那些号码，比如68，666，888都是“幸运号码”！但是这种“幸运号码”总是太少了，比如在[1,100]的区间内就只有6个（6，8，66，68，86，88），于是他又定义了一种“近似幸运号码”。lxhgww规定，凡是“幸运号码”的倍数都是“近似幸运号码”，当然，任何的“幸运号码”也都是“近似幸运号码”，比如12，16，666都是“近似幸运号码”。现在lxhgww想知道在一段闭区间[a, b]内，“近似幸运号码”的个数。

Input

输入数据是一行，包括2个数字a和b

Output

输出数据是一行，包括1个数字，表示在闭区间[a, b]内“近似幸运号码”的个数

Sample Input

【样例输入1】
1 10
【样例输入2】
1234 4321

Sample Output

【样例输出1】
2
【样例输出2】
809

HINT

【数据范围】
对于30%的数据，保证1 < =a < =b < =1000000
对于100%的数据，保证1 < =a < =b < =10000000000

Source

Day1

题解：

容斥原理＋爆搜。

记得开double或unsigned long long。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define LL unsigned long long
 4 LL sum,cc[2100],lc,a,b;
 5 bool vis[2100];
 6 LL Gcd(LL aa,LL bb){if(bb==0)return aa;else return Gcd(bb,aa%bb);}
 7 void DFS(LL x,LL y,LL gs,LL lcm, LL gcd,LL ii)
 8 {
 9     LL LCM,GCD,i;
10     //if(lcm>x||lcm>y)return;
11     if(lcm>x&&lcm>y)return;
12     if(gs>0)
13     {
14         if(gs%2!=0)sum+=((LL)(y/lcm)-(LL)(x/lcm));
15         else sum-=((LL)(y/lcm)-(LL)(x/lcm));
16     }
17     if(gs==lc+1||ii+1>lc)return;
18     for(i=ii+1;i<=lc;i++)
19     {
20         if(vis[i]==false)
21         {
22             vis[i]=true;
23             LCM=lcm;GCD=gcd;
24             gcd=Gcd(lcm,cc[i]);lcm=(lcm*cc[i])/gcd;
25             DFS(x,y,gs+1,lcm,gcd,i);
26             lcm=LCM;gcd=GCD;
27             vis[i]=false;
28         }
29     }
30 }
31 LL calc(LL x,LL y)
32 {
33     /*for(i=1;i<=lc;i++)
34     {
35         tot=0;
36         DFS(x);
37     }*/
38     memset(vis,false,sizeof(vis));sum=0;
39     DFS(x-1,y,0,1,1,0);
40     return sum;
41 }
42 void dfs(LL k)
43 {
44     if(k>b)return;
45     if(k!=0)cc[++lc]=k;
46     dfs(k*10+6);
47     dfs(k*10+8);
48 }
49 int main()
50 {
51     LL len,i;
52     scanf("%lld %lld",&a,&b);
53     memset(cc,0,sizeof(cc));lc=0;
54     dfs(0);
55     sort(cc+1,cc+lc+1);
56     len=unique(cc+1,cc+lc+1)-(cc+1);
57     for(i=1;i<=len/2;i++)swap(cc[i],cc[len-i+1]);
58     lc=len;
59     printf("%lld",calc(a,b));
60     return 0;
61 }

Bzoj 1853: [Scoi2010]幸运数字 容斥原理,深搜