[SCOI2010 第一试 幸运数字]容斥原理

【题目】

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 【算法分析】
该题使用容斥原理，把符合的数先都DFS出来，然后把互为约数的，大的那个删掉。
最后需要注意各种不要超范围。
因为题目给的范围异常猥琐，b*b都会爆long long，所以需要各种先除后乘。
【其他】
由于之前因为程序中注释处溢出一直TLE，然后围观与标程有什么不同，以至于已经和标程没啥区别了
= =。。。Orz。。。
【CODE】
#include #include #include #include using namespace std;
typedef long long lld;
const int N=20000;
lld a,b,tot=0,ans,X;
lld list[N];

void makelist(int dep,lld x){
if (x>b) return;
list[tot++]=x;
makelist(dep+1,x*10+6);
makelist(dep+1,x*10+8);
}

lld gcd(lld x,lld y){
lld z;
while (y){
z=x%y;
x=y;
y=z;
}
return x;
}

void dfs(int st,int times,lld num){
int i; lld g;
for (i=st;i>=1;i–){
g=gcd(list[i],num);
if (num/g<=X/list[i]){ // 改成if (num/g*list[i]<=X)的话 ，会因溢出而TLE在那里！
if (times&1) ans-=X/(num/g*list[i]);
else ans+=X/(num/g*list[i]);
dfs(i-1,times+1,num/g*list[i]);
}
}
}

lld cal(lld x){
if (x<=5) return 0;
ans=0; X=x;
dfs(tot-1,0,1);
return ans;
}

int main(){
freopen("luckynumber.in","r",stdin);
freopen("luckynumber.out","w",stdout);
cin >> a >> b;
makelist(0,0);
sort(list,list+tot);
for (int i=2;i bool flag=false;
for (int j=1;j if (list[i]%list[j]==0){
flag=true;
break;
}
if (flag){
for (int j=i;j+1 list[j]=list[j+1];
tot–;
i–;
}
}
cout << cal(b)-cal(a-1) << endl;
}