首页 > 代码库 > [SCOI2010]幸运数字
[SCOI2010]幸运数字
题目背景
四川NOI省选2010
题目描述
在中国，很多人都把6和8视为是幸运数字！lxhgww也这样认为，于是他定义自己的“幸运号码”是十进制表示中只包含数字6和8的那些号码，比如68，666，888都是“幸运号码”！但是这种“幸运号码”总是太少了，比如在[1,100]的区间内就只有6个（6，8，66，68，86，88），于是他又定义了一种“近似幸运号码”。lxhgww规定，凡是“幸运号码”的倍数都是“近似幸运号码”，当然，任何的“幸运号码”也都是“近似幸运号码”，比如12，16，666都是“近似幸运号码”。
现在lxhgww想知道在一段闭区间[a, b]内，“近似幸运号码”的个数。
输入输出格式
输入格式：
输入数据是一行，包括2个数字a和b
输出格式：
输出数据是一行，包括1个数字，表示在闭区间[a, b]内“近似幸运号码”的个数
输入输出样例
输入样例#1：
1 10
输出样例#1：
2
说明
对于30%的数据，保证1<=a<=b<=1000000
对于100%的数据，保证1<=a<=b<=10000000000
思路：打表+容斥原理+剪枝
先打一张幸运数字的表；
然后容斥原理求值；
剪枝：有些（是前面的幸运数字的倍数）幸运数字是无用的。
从大到小排。
超出边界的最小公倍数是无用的。
代码实现：
1 #include<cstdio> 2 #include<algorithm> 3 #define LL long long 4 using namespace std; 5 LL l,r,ans; 6 LL a,b; 7 LL s[3000],ss; 8 LL fs[3000],fss; 9 LL lch,ret;10 char ch[30];11 LL read(){12 while(ch[0]=getchar(),ch[0]<‘0‘||ch[0]>‘9‘);13 lch=1,ret=ch[0]-‘0‘;14 while(ch[lch]=getchar(),ch[lch]>=‘0‘&&ch[lch]<=‘9‘) ret=ret*10+ch[lch]-‘0‘,lch++;15 return ret;16 }17 void write(LL x){18 if(!x) return;19 write(x/10);20 putchar(x%10+‘0‘);21 }22 void dfs(LL x){23 if(x>r) return;24 if(x) s[ss++]=x;25 dfs(x*10+6);26 dfs(x*10+8);27 }28 inline LL gcd(LL x,LL y){return y?gcd(y,x%y):x;}29 void get_ans(LL k,LL x,LL y){30 if(x>r) return;31 if(k) ans+=(k&1)?r/x-(l-1)/x:(l-1)/x-r/x;32 for(LL i=y;i<ss;i++){33 LL t=x/gcd(x,s[i]);34 if(t<=r/s[i]) get_ans(k+1,t*s[i],i+1);35 }36 }37 int main(){38 freopen("luckynumber.in","r",stdin);39 freopen("luckynumber.out","w",stdout);40 l=read(),r=read();41 dfs(0);42 sort(s,s+ss);43 for(LL i=0;i<ss;i++){44 for(LL j=0;j<fss;j++)45 if(s[i]%fs[j]==0){s[i]=0;break;}46 if(s[i]) fs[fss++]=s[i];47 }48 ss=fss;49 for(int i=0;i<ss;i++) s[i]=fs[ss-i-1];50 get_ans(0,1,0);51 if(!ans) putchar(‘0‘);52 write(ans);53 putchar(‘\n‘);54 return 0;55 }
| bzoj | 74 | 1950429 | J_william | 872 KB | 672 MS | C++ | 1188 B | 2017-03-26 18:04:28 |
LONG LONG 真恶心！
题目来源：洛谷,bzoj
[SCOI2010]幸运数字
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。