P9407 [POI2020-2021R3] Suma liczb pierwszych

· · 题解

考虑 n 小的时候怎么做。

直接预处理出 n 以内的所有质数，做一个前缀和，然后双指针即可，这一部分是简单的，复杂度 \mathcal{O}(n)。

当 n 大时这样显然寄了，考虑用这种做法做到上限为 L，即解决所有答案右端点在 [1,L] 内的情况，这个时候，答案右端点显然在 (L,n] 内，不难发现，满足如上情况时答案的质数个数只有 \mathcal{O}(\dfrac{n}{L}) 级别。

考虑枚举质数个数，设现在枚举的质数个数为 t，则答案肯定在 \dfrac{n}{t} 附近，设答案区间的左右端点落在 [l',r'] 内，由素数密度我们可以知道，r'-l'=\mathcal{O}(t\ln n)。因此我们暴力的范围最终很小，像上面那样再做双指针即可。

时间复杂度 \mathcal{O}(L+\dfrac{n^2}{L^2}\ln n\operatorname{check}(n))，其中 \operatorname{check}(n) 为检验一个大数 n 是否为质数的复杂度，假如我们用米勒拉宾算法来求质数，那么取 L=n^{\frac{2}{3}}\log n 可以做到复杂度 \mathcal{O}({n^\frac{2}{3}\log n})（这里让 \ln n 和 \log n 同级）。

当然数字较大的时候一个一个判素数还是太笨蛋了，因为最终的暴力区间不会很大，因此可以考虑使用筛区间质数的方法，即：假如我们要筛 [l,r] 内的质数，我们枚举 \sqrt{r} 内的质数去更新当前区间的质数信息，显然枚举的质数个数不会很多。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,pre[5000005],prp[5000005],cnt;
bitset<100000005> f;
bitset<200005> chk;
void solve(int l,int r)
{
    chk.reset();
    // memset(chk,0,sizeof(chk));
    for(int i=1;i<=cnt&&prp[i]*prp[i]<=r;i++)
    {
        // cerr<<"????"<<i<<"\n";
        for(int j=(l+(prp[i]-1))/prp[i];j*prp[i]<=r;j++)
        {
            // cerr<<j*prp[i]<<"\n";
            chk[prp[i]*j-l]=1;
        }
    }
}
int findnxt(int x,int g)
{
    int i=x+1;
    while(chk[i-g]) i++;
    return i;
}
int findpre(int x,int g)
{
    int i=x-1;
    while(i>=2&&chk[i-g]) i--;
    return i;
}
bool check(int n)
{
    if(n==1) return 0; 
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0) return 0;
    }
    return 1;
}
signed main()
{
    cin>>n;
    for(int i=2;i<=20000000&&i<=n;i++)
    {
        if(!f[i]) prp[++cnt]=i;
        for(int j=1;j<=cnt&&i*prp[j]<=20000000&&i<=n;j++)
        {
            f[i*prp[j]]=1;
            if(i%prp[j]==0) break ;
        }
    }
    for(int i=1;i<=cnt;i++)
    {
        pre[i]=pre[i-1]+prp[i];
    }
    int l=1;
    if(n==1)
    {
        cout<<"NIE";
        return 0;
    }
    if(check(n))
    {
        cout<<n<<" "<<n;
        return 0;
    }
    for(int i=1;i<=cnt;i++)
    {
        while(l<i&&pre[i]-pre[l-1]>n) l++;
        if(pre[i]-pre[l-1]==n)
        {
            cout<<prp[l]<<" "<<prp[i]<<"\n";
            return 0;
        }
    }
    for(int i=2;i<=5000;i++)
    {
        int t=n/i;
        int base=20;
        if(i<=5) base=200;
        int LIM=max(t-max(i*base,100000ll),1ll);
        solve(LIM,t+max(i*base,100000ll));
        int r=findnxt(t,LIM);
        vector<int> pp;
        pp.emplace_back(r);
        if(r<=2e7) break ;
        int sum=r,cnt=1,l=r,it=0;
        while(cnt<i) l=findpre(l,LIM),sum+=l,cnt++,pp.emplace_back(l);
        // cerr<<"???"<<t<<" "<<l<<" "<<r<<"\n";
        reverse(pp.begin(),pp.end());
        while(sum<n) sum-=l,l=pp[++it],r=findnxt(r,LIM),sum+=r,pp.emplace_back(r);
        if(sum==n)
        {
            cout<<l<<" "<<r;
            cerr<<"\n"<<clock()*1.0/CLOCKS_PER_SEC;
            return 0;
        } 
    }
    cout<<"NIE";
}