p8795 选素数

· · 题解

数论好题，练习线性筛xxs的绝世好题。

一次操作的做法

放个结论：当我只有一次操作时，设结果为 n ， n 的最大质因数为 p ，初始值为 x ，则 x_{min}=n-p+1 。

加一不难理解，但是为什么我要减的是最大质因数呢？

原因显然。

首先，之所以是质因数，是因为废话我选的是质数且它一定是 n 的因数。

接着，由于我要使值最小，我减的显然得最大，于是就要用最大质因数。

因此，当只有一次操作时，我可以直接质因数分解，然后取最大质因数套公式。

时间复杂度 O(\sqrt{n})

代码不给

二次操作的做法

还是看上面那个公式： x_{min}=n-p+1

不难想到 x_{max}=n 。

那么此时我只要对最小最大之间所有数遍历一遍，每一个找最小值，总的再取最小值即可。

时间复杂度 O(n\sqrt{n}) ，显然通不过，故代码不给。

考虑如何筛最大质因数，使复杂度降到 O(n) 。

再来个公式：设两个非 01 自然数为 n 和 m ，一个质数为 p ，满足 n=m \times p ， f_i 表示 i 的最大质因数，那么 f_n = \max(f_m,p) 。

证明也十分简单： n 的质因数显然由 m 的质因数与 p 组成，因此 n 的最大质因数显然等于 m 的质因数与 p 的最大值。

看一看上面那个公式，是不是想到怎么筛了？

没错！xxs 线性筛！

线性筛正是用已筛过的数（即上文 m ）乘以已得到的质数（即 p ）来筛其他数（即 n ）!

于是，我们可以就可以用线性筛筛出最大质因数了。

根据线性筛的性质， p 显然是 n 的最小质因数，因此不用再取最大值。

时间复杂度 O(n) ，可以通过此题（话说最优解也就这样了吧）

注意特殊情况需要特判：当 n 是质数（或是 1 ）时，最大质因数只能是他自己本身（或没有），而题目要求是 选一个比 x 小的素数，不符合题意，直接输出 -1 。

代码如下：

#include<bits/stdc++.h>
#define ri register int
#define maxn 1000005
#define inf 0xffffff
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-48;
        ch=getchar();
    }
    return x*f;
}
inline void write(int n){
    if(n<0){
        putchar('-');
        n=-n;
    }
    if(n>9)
        write(n/10);
    putchar(n%10+'0');
}
int n;
int np[maxn];
vector<int>pri;
void init(){
    for(ri i=2;i<=n;i++){
        if(!np[i]){
            pri.push_back(i);
            np[i]=i;
        }
        for(auto j:pri){
            if(i*j>n)break;
            np[i*j]=max(max(np[i*j],j),np[i]);
            if(!(i%j))break;
        }
    }
}
//zy:~~kunkun~~zhiyin(max)(+1)
int zy[maxn];
signed main(){
    n=read();
    init();
    for(ri i=2;i<=n;i++){
        if(np[i]^i)zy[i]=i-np[i]+1;
        else zy[i]=i;
    }
    int mini=inf;
    if(np[n]==n||!np[n])write(-1);
    else{
        for(ri i=n-np[n]+1;i<=n;i++)if(np[i]!=i)mini=min(mini,zy[i]);
        write(mini);
    }
    return 0;
}

文后赠礼：筛质因数

既然我用可以筛出最大质因数，那我是不是还可以筛质因数？

一个很显然的思路是我在筛的时候把其他质因数都复制过去，这样虽然简单粗暴易懂，但是时间空间复杂度都爆炸，不划算。

但是，用上链表的思想，我是不是可以只表示当前乘上的质数，而用指针指向质数乘上的数的位置？

这样筛下来，由于一个数只能被筛一次，最后会形成 k 棵有根树（其中 k 为小于等于 n 的质数数量），从编号为 n 的节点一直爬到根节点，路径上所有数字之积即为 n ，而路径上的都是 n 的质因数！

于是，我可以实现 O(n) 预处理， O(q \log n) 查询质因数，彻底告别 O(q \sqrt{n}) （ O(q \log n) 是最坏情况下的，实际上绝对没有这么大）。

思路放这，代码不给了，有意者撕私我。