提高培优班Day7 T2 丑数题解

常规
,
1

丑数：

题目大意：

给定 k 个质数，求第 n 个有给定质数因子的数，数据随机

对于50%的数据，保证 n <=100000 ，素数在1000以内均匀随机

对于100%的数据，保证 n<= 10^9 , k<=100 ，素数在1000000以内均匀随机， T<=50

保证输出不会超过MAX_LONG_INT

Sol:

这个部分分和没有一样，直接正解

事实上只有两个数据点/cf

令答案为 p

由于我们都不会做，而随着 p 的增大， n 也会变大，考虑二分数字 p

思考check函数，对于一个数 x ，容易得出在 小于 p 的范围内，以 x 为因子的数有 p/x 个 ,然后我们就可以根据容斥原理得出小于 p 的范围内有多少以给定素数构成的数了，相当于我们的排名

推素数的时候建议用dfs，就算滚动递推也会爆空间

dfs注意剪枝，要注意先给素数排序优化搜索顺序

Code:

#include<bits/stdc++.h>
using namespace std;
int T;
typedef long long ll;
ll prime[105],mid,tot;
bool could;
ll n,k;
bool cmp(ll a,ll b){
	return a>b;
}
void dfs(int w,int cnt,int all,ll last){
	if(cnt==all){
		if(cnt&1)	tot+=mid/last;
		else tot-=mid/last;
		could=1;
		return ;
	}
	if(w+cnt-all-1>k)	return ;
	dfs(w+1,cnt,all,last);
	if(last<=mid/prime[w])	dfs(w+1,cnt,all+1,last*prime[w]);
}
bool check(){
	tot=0;
	for(int i=1;i<=k;i++){
		could=0;
		dfs(1,i,0,1ll);
		if((!(i&1))&&tot>=n)	return 1;
		if(!could)	break;
	}
	return 0;
}
int main(){
	cin>>T;
	while(T--){
		cin>>n>>k;
		for(int i=1;i<=k;i++)	scanf("%lld",&prime[i]);
		sort(prime+1,prime+1+k,cmp);
		ll l=0,r=1ll*INT_MAX*4000,ans=0;
		while(l<=r){
			mid=l+(r-l)/2;
			if(check())	r=mid-1,ans=mid;
			else l=mid+1;
		}
		cout<<ans<<"\n";
	}
	return 0;
}
1 个赞