[原创]BZOJ1853 [Scoi2010]幸运数字 [容斥原理]【组合数学】
[原创]BZOJ1853 [Scoi2010]幸运数字 [容斥原理]【组合数学】
2017-02-13 22:15:06 Tabris_ 阅读数:634
博客爬取于2020-06-14 22:41:35
以下为正文
版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/55058123
题目连接:https://vjudge.net/problem/HYSBZ-1853
------------------------------------------------------------------------------------------------------------.
1853: [Scoi2010]幸运数字
Time Limit: 2 Sec Memory Limit: 64 MB
Submit: 2284 Solved: 834
[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
------------------------------------------------------------------------------------------------------------.
首处理出所有的幸运数字,
只有个.
然后找到这些数中的"幸运素数"(就是这些数组成的序列中不能被其他元素整除的数~~(类似线性基?!)~~)
找到这些数,那么 其实就把这个问题就是成求[a,b]内那些"幸运素数"的倍数有多少个就好了.
答案就是
很明显的一个容斥原理,
上述问题很容易 不再赘述
附本题代码
------------------------------------------------------------------------------------------------------------.
1 | LL l,r,a[10000],cnt,ans; |