自动搬运

查看原文

来自洛谷，原作者为

	ChrysanthBlossom 讹波提的！

搬运于2025-08-24 22:42:33，当前版本为作者最后更新于2022-11-05 21:08:28，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

数论好题，练习线性筛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)$ 是最坏情况下的，实际上绝对没有这么大）。

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