Na2CO3_qwq【绿钩】更新时间：2022-06-18 16:48:43

在 Ta 的博客查看

题目分析

本题考查贪心 + 暴力。

思路：每次就找到它最大的因数，因为只能剩下一行，这样剩下的数就是最大的。

我呢，反过来枚举 nn 最大的因数，并把 nn 变成最大的因数并累积答案。

详情见代码。

#include<iostream>
#include<cmath>//sqrt函数需要用到
using namespace std;
int n,ans=1;//ans初始化成1，是因为最后一次需要+1，这个1提前加上。
int main(){
    cin>>n;//输入
    while(n>1){//循环
        ans=ans+n;//累加
        bool flag=true;//定义布尔型变量，判断是否为质数。
        for(int i=n-1;i>=sqrt(n);i--){//从大到小枚举，比较直观，就是费时间，容易TLE。
            if(n%i==0){//如果整除
                n=i;//把n变成最大因数
                flag=false;//flag变成false
                break;//跳出循环
            }
        }
        if(flag==true){//如果flag仍为true证明是质数
            cout<<ans<<endl;return 0;//输出答案，结束程序
        }
    }
    cout<<ans<<endl;//输出答案
    return 0;//养成好习惯。
}

搬运自己的题解

https://www.luogu.com.cn/record/77558348