10分求助
查看原帖
10分求助
499231
Jacky2009楼主2022/5/11 23:26
#include<bits/stdc++.h>
using namespace std;
vector<int>li,li2,tmp;
int lis[100005];
int mark=2,start=0;
int work(int x){
	tmp.clear();
	for(int i=4;i<li2.size();i++){
		if(li2[i]>x)break;
		for(int j=1;j*li2[i]<=x;j++)tmp.push_back(j*li2[i]);
	}
	unique(tmp.begin(),tmp.end());
	int cnt=0;
	for(int i=0;i<tmp.size();i++)cnt+=(tmp[i]%6==0||tmp[i]%8==0||tmp[i]%68==0||tmp[i]%86==0);
	int cnt2=x/6+x/8+x/68+x/86-x/24-x/136-x/2924-x/258-x/204-x/344+x/408+x/1032+x/8772+x/5848-x/17544;
	cnt2-=cnt;
//	cout<<cnt2+(tmp.size())<<endl;
	return cnt2+tmp.size();
}
int main(){
	li.push_back(6);
	li.push_back(8);
	for(int i=1;i<=8;i++){
		for(int j=start;j<=start+mark-1;j++){
			li.push_back(li[j]*10+6);
			li.push_back(li[j]*10+8);
		}
		start+=mark;
		mark*=2;
		
	}
	for(int i=0;i<li.size();i++){
		//cout<<li[i]<<" ";
		if(lis[i]==-1)continue;
		for(int j=i+1;j<li.size();j++)if(li[j]%li[i]==0)lis[j]=-1;
	}
	for(int i=0;i<li.size();i++)if(lis[i]==0)li2.push_back(li[i]);
	int a,b;
	cin>>a>>b;
	int a2=work(a),b2=work(b);
	int res;
	if(binary_search(li2.begin(),li2.end(),a2))res=b2-a2+1;
	else res=b2-a2;
	cout<<res;
}

2022/5/11 23:26
加载中...