【BZOJ 1853】 1853: [Scoi2010]幸运数字 (容斥原理)

1853: [Scoi2010]幸运数字

Time Limit: 2 Sec  Memory Limit: 64 MB
Submit: 2472  Solved: 911

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

【分析】

  这道题,是很经典的容斥。只是复杂度有些玄学。

  就是现求出所有lucky number,然后对于比如说66是6的倍数,66可以删掉。

  然后找6的倍数,+1,8的倍数+1,6和8的公倍数,-1。。。。【就是这样容斥

  你lucky number排序后从大到小枚举,超过b就return,就可以过了。

  【对了,不要直接求lcm,达到了10^10,会爆LL,我就这样超时了。。

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 using namespace std;
 7 #define LL long long
 8 
 9 LL a,b;
10 LL w[2500];
11 void ffind(LL x)
12 {
13     if(x*10+6<=b) {w[++w[0]]=x*10+6;ffind(x*10+6);}
14     if(x*10+8<=b) {w[++w[0]]=x*10+8;ffind(x*10+8);}
15 }
16 
17 LL gcd(LL a,LL b)
18 {
19     if(b==0) return a;
20     return gcd(b,a%b);
21 }
22 LL ans=0;
23 void dfs(LL x,LL y,LL f)
24 {
25     if(x==0)
26     {
27         ans+=f*(b/y-(a-1)/y);
28         return;
29     }
30     LL g=gcd(y,w[x]);
31     if(y/g<=b/w[x]) dfs(x-1,y/g*w[x],-f);
32     dfs(x-1,y,f);
33 }
34 
35 int main()
36 {
37     scanf("%lld%lld",&a,&b);
38     w[0]=0;ffind(0);
39     sort(w+1,w+1+w[0]);
40     int nw=0;
41     for(int i=1;i<=w[0];i++)
42     {
43         if(w[i]==-1) continue;
44         w[++nw]=w[i];
45         for(int j=i+1;j<=w[0];j++) if(w[j]!=-1&&w[j]%w[i]==0)
46         {
47             w[j]=-1;
48         }
49     }w[0]=nw;
50     dfs(w[0],1,-1);
51     printf("%lld
",b-a+1+ans);
52     return 0;
53 }
View Code

2017-04-19 20:32:25

原文地址:https://www.cnblogs.com/Konjakmoyu/p/6735710.html