[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;
}

加入对话

2条评论

  1. 先膜拜下,请问大神,我以前做的容斥的水题,都是那种n<=15个的,所以我枚举的复杂度是2^15最多,但此题,数据我估计最多800多个,2^800如果能够dfs呢?

留下评论

回复 edward_mj 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注