H-无尽大军 2019年安徽大学ACM/ICPC实验室新生赛（公开赛）

一道简单的递推题目。基于贪心的思想，要想花费少，应该尽可能采用翻倍再的方法，比如100的话先构造出50，再翻倍，99的话，构造出33，翻倍再一次。因此对n来说，找到它最小的质因子i，n/i就是构造n之前需要构造的军队。（题目数据范围也隐性提示了一下做法）。
个人习惯用dfs写这类问题。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n;
ll dfs(ll n) /**< 贪心思想 */
{
    if(n==1)
        return 0;
    ll i;
    for(i=2; i*i<=n; i++)/**< 找到n最小质因子 */
    {
        if(n%i==0)
            break;
    }
    if(i*i<=n)
        return i+dfs(n/i);/**< 花费正好是质因子的值，总共***i-1次，第一次花费2 */
    else
        return n;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j;
    cin>>n;
    cout<<dfs(n);
    return 0;
}