1. 题目

传送门= ̄ω ̄=

2. 题解

跑一遍素数筛,筛出每个数字的所有质因数,存在数组里。
然后$f(i)=min(f(i-1),f(i/p))+1$,$p$是$i$的质因数。

代码:

#include <bits/stdc++.h>
using namespace std;
int n,f[1000005],d[1000005][25],dc[1000005];
bool book[1000005];
int main()
{
    for(int i=2;i<=1000000;i++)
        if(!book[i])
            for(int j=i;j<=1000000;j+=i)
                book[j]=1,d[j][dc[j]++]=i;
    for(int i=2;i<=1000000;i++)
    {
        f[i]=f[i-1]+1;
        for(int j=0;j<dc[i];j++)f[i]=min(f[i],f[i/d[i][j]]+1);
    }
    while(~scanf("%d",&n))printf("%d\n",f[n]);
    return 0;
}
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *