题解 P2618 【数字工程】

· · 题解

虽然题目底下的说明里的解题思路是DP的，但是坐在隔壁的wzp大佬看了一眼秒了此题，觉得这是一道简单的宽搜题，为了实现大佬的思路，本蒟蒻特地写了一份宽搜的代码。

宽搜的思路很简单，每一个数都可以向减一或除以自己的某一个素因子拓展，然后就是基本的宽搜了，当搜到1的时候退出，否则继续拓展。

素因子可以预先处理出来，跟下面的dp做法是一样的。可以用埃氏筛直接筛好，欧拉筛好像也可以。

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,a,prime[1000005][25],size[1000001],f[1000000],l,r,ans[1000000];//prime[i][j]表示数i的第j大的素因子，size[i]表示数i的素因子个数，ans记录到i个点时所耗能量
bool pri[1000005],vis[1000000];//vis判重，pri判质数

inline void bfs() { //宽搜
    if(f[l]==1) { //当搜到1的时候退出
        cout<<ans[l]<<'\n';
        l=r+10;//退出宽搜
        return;
    }
    if(!vis[f[l]-1]) { //判重
        vis[f[l]-1]=true;//向减一拓展
        f[++r]=f[l]-1;
        ans[r]=ans[l]+1;
    }
    for(int i=1; i<=size[f[l]]; i++) { //向除某一个素因数拓展
        if(!vis[f[l]/prime[f[l]][i]]) {
            f[++r]=f[l]/prime[f[l]][i];
            ans[r]=ans[l]+1;
            vis[f[r]]=true;
        }
    }
    ++l;
    return;
}

inline int get(int x) {
    memset(f,0,sizeof f);
    memset(ans,0,sizeof ans);
    memset(vis,0,sizeof vis);
    l=0;
    r=0;//初始化
    f[0]=x;
    while(l<=r) {
        bfs();
    }
    return 1;
}

int main() {
    ios::sync_with_stdio(false);//关同步，可以稍微优化一点
    for(int i=2; i<=1000000; i++) { //埃氏筛筛质数
        if(!pri[i]) {
            for(int j=i*2; j<=1000000; j+=i) {
                pri[j]=true;
                prime[j][++size[j]]=i;//筛素因子
            }
            prime[i][++size[i]]=i;//筛素因子
        }
    }
    while(cin>>n) { //读入
        get(n);
    }
    return 0;
}