首页 > 代码库 > AC日记——[SCOI2010]幸运数字 bzoj 1853

AC日记——[SCOI2010]幸运数字 bzoj 1853

2024-09-10 17:32:32   216人阅读

1853: [Scoi2010]幸运数字

Time Limit: 2 Sec  Memory Limit: 64 MB
Submit: 2405  Solved: 887
[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

 
思路：
　　挨千刀的搜索题；
　　考试时想到了搜索但是看了复杂度就没去打；
　　结果特么真的是搜索；
　　用搜索实现容斥；
 
来，上代码：
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;long long int l,r,table[40000],num,ans;void pdfs(long long int now){    if(now>r) return ;    table[++num]=now;    pdfs(now*10+6),pdfs(now*10+8);}void pre(){    pdfs(6),pdfs(8);    sort(table+1,table+num+1);    long long new_table[40000],new_num=0;    for(int i=1;i<=num;i++)    {        for(int j=1;j<i;j++)        {            if(table[j]==0) continue;            if(table[i]%table[j]==0)            {                table[i]=0;                break;            }        }        if(table[i]) new_table[++new_num]=table[i];    }    num=new_num;    for(int i=1;i<=num;i++) table[num-i+1]=new_table[i];    return ;}inline long long int gcd(long long int x,long long int y){    return y?gcd(y,x%y):x;}void dfs(long long int now,int p,bool lev){    if(now>r) return ;    if(lev) ans+=r/now,ans-=l/now;    else ans-=r/now,ans+=l/now;    for(int i=p;i<=num;i++)    {        double pos=now/gcd(now,table[i]);        if(pos<=r/table[i]) dfs(pos*table[i],i+1,lev^1);    }}int main(){    freopen("luckynumber.in","r",stdin);    freopen("luckynumber.out","w",stdout);    cin>>l>>r;    pre(),l--;    for(int i=1;i<=num;i++) dfs(table[i],i+1,true);    cout<<ans;    fclose(stdin),fclose(stdout);    return 0;}

 

AC日记——[SCOI2010]幸运数字 bzoj 1853


联系
我们