P2618 数字工程

题目链接

Solution

不妨转换一下思路，(n) -> (1) 和 (1) -> (n) 是等价的。设 (f_i) 表示从 (1) 到 (i) 的最少步数，那么两种操作变成了：

(1.) 加上 (1)

(2.) 乘以一个素数

设 (prim) 是已经筛出的 (≤10^6) 的素数（筛的时候 (O(n sqrt{n})) 就行，不需要筛法），转移方程式：

[f_{i*prim_j}=max(f_{i*prim_j}, f_i+1) (i * prim_j ≤ 10^6) ]

[f_{i+1}=max(f_{i+1}, f_i+1) ]

数据范围有整整 (10^6)，看起来非常不好做，然而只需要暴力预处理 (f) 数组，像这样循环：

for(int j = 1; i * prim[j] <= 1000000 && j <= cnt; j++)

可以优化掉不少不必要的操作，多测时直接回答询问，就能跑得很快。

Code

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

const int N = 2333333;
int n, cnt = 0, f[N], prim[N];

int main()
{
    for(int i = 2; i <= 1000000; i++)
    {
        int fl = 1;
        for(int j = 2; j <= sqrt(i); j++)
            if(i % j == 0) { fl = 0; break; }
        if(fl == 1) prim[++cnt] = i;
    }
    memset(f, 0x3f, sizeof(f));
    f[1] = 0;
    for(int i = 1; i <= 1000000; i++)
    {
        for(int j = 1; i * prim[j] <= 1000000 && j <= cnt; j++)
            f[i * prim[j]] = min(f[i * prim[j]], f[i] + 1);
        f[i + 1] = min(f[i + 1], f[i] + 1);
    }
    while(cin >> n) printf("%d
", f[n]);
    return 0;
}