自动搬运

查看原文

来自洛谷，原作者为

	HYXLE ㅤ

搬运于2025-08-24 22:23:40，当前版本为作者最后更新于2024-11-01 19:52:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

思考

定义数字 $x$ 的最小操作次数为 $f(x)$ 。

通过显然的观察可以得到，当 $x$ 递增时，$f(x)$ 也是递增的，且若某个数 $x$ 无解，则大于 $x$ 的数都是无解。

显然想到二分，对于每种答案，求出是这个答案的 $a$ 的区间是什么，查询时直接二分出 $x$ 属于哪个区间即可。

不难发现 $f(x) \leq x$，所以可以直接使用结构体存储。

如何二分呢？

显然可以记录一个 $lst$ 表示上一种答案的区间的右端点是哪个，然后二分这种答案的右端点 $r$ 。接着枚举每个素数 $p$ ，把操作 $p$ 后的数字求出来，若存在某个素数使得求出来的数小于等于 $lst$ ，则这个 $r$ 是合法的，反之则不合法。

注意刚开始的时候先将数组 $p$ 去重。

时间复杂度作者太菜了不会证明，希望有人能证明一下。

代码

#include<bits/stdc++.h>
#define ll long long
#define R register
using namespace std;
const int N=1e5+5,M=1e7+5;
struct node{int l,r;}ans[N*100];
int n,q,pr[N];
inline bool check(int x,int lst){
	int mn=x;
	for(R int i=1;i<=n;++i){
		mn=min(mn,x-x%pr[i]);
		if(mn<lst)return 1;
	}
	return 0;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(R int i=1;i<=n;++i){
		cin>>pr[i];
	}
	sort(pr+1,pr+n+1);
	n=unique(pr+1,pr+n+1)-pr-1;
	int tot=0;
	for(int l=1,res,r;l<=M-5;l=res+1){
		int ls=l;r=M-5;res=-1;
		while(ls<=r){
			int mid=ls+r>>1;
			if(check(mid,l))ls=mid+1,res=mid;
			else r=mid-1;
		}
		if(res==-1)break;
		ans[++tot]={l,res};
	}
	while(q--){
		int x;cin>>x;
		if(x==0)cout<<0<<'\n';
		else{
			int l=1,r=tot;
			if(ans[r].r<x){
				cout<<"oo\n";continue;
			}
			int res=tot;
			while(l<=r){
				int mid=l+r+1>>1;
				if(ans[mid].l<=x)res=mid,l=mid+1;
				else r=mid-1;
			}
			cout<<res<<'\n';
		}
	}
	return 0;
}