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;
}
查看11道真题和解析
