solution of P6756

f__k_sheep · 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;
}