「BZOJ2393」Cirno的完美算数教室
Description
~Cirno发现了一种baka数，这种数呢~只含有2和⑨两种数字~~
现在Cirno想知道~一个区间中~~有多少个数能被baka数整除~
但是Cirno这么天才的妖精才不屑去数啦
只能依靠聪明的你咯。
Input
一行正整数L R
( 1 < L < R < 10^10)
Output
一个正整数，代表所求的答案
Sample Input
1 100
Sample Output
58
HINT
此题数据范围应该是10^9
10^9中只含2和9的数，且不被其它这样的数整除的baka数只有30个左右
于是我们可以利用容斥原理，加上奇数个集合的并，减去偶数个集合的并
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define ll long long #define N 2001 using namespace std; ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} int l,r; int t,n,m,ans; ll a[N],b[N]; bool vis[N]; void pre(int x,int y) { if(x>t||y>r)return; if(x>0)a[++m]=y; pre(x+1,y*10+2); pre(x+1,y*10+9); } void dfs(int x,int y,ll z) { if(x>n) { if(y&1)ans+=r/z-(l-1)/z; else if(y)ans-=r/z-(l-1)/z; return; } dfs(x+1,y,z); ll next=a[x]*z/gcd(a[x],z); if(next<=r) dfs(x+1,y+1,next); } int main() { scanf("%d%d",&l,&r); t=(int)(log(r)/log(10))+1; pre(0,0); sort(a+1,a+m+1); for(int i=1;i<=m;i++) if(!vis[i]) { b[++n]=a[i]; for(int j=i+1;j<=m;j++) if(!(a[j]%a[i])) vis[j]=1; } for(int i=1;i<=n;i++) a[n-i+1]=b[i]; dfs(1,0,1); printf("%lld",ans); return 0; } |
计数器 9787621
OI 课件=>
OI 课件=>
素数是什么鬼啊…应该是那些不能被其他只含2和9整除的数？
这题和只含2和9的质数有什么关系？
求区间内 质因数只有2，9，29。。。这样的数 个数
92是质数吗？