题目描述
时钟指向0点，又是新的一天。今天是七夕节，看着朋友圈牛云、牛郭、牛陈、牛余、牛lan等脱单牛准点发送的虐牛图，牛牛心理丝毫没有波动，因为他在协助科研人员制作新牛病毒的疫苗！
手机突然传来消息提醒：
七夕节有空出来一起吃饭吗？好久没见你了，想见你！——牛妹（清楚姐姐扮演）
疫苗的研发已经剩下最后一个难关：
定义一个函数 f(n) 为将 n 进行严格的因数分解(因数不重复，且分解的因数个数要大于1)后，使得所分解的因数之和最小的值，现在给出一个正整数 n，能否算出 f(n) ?
牛牛太想和牛妹一起过七夕节了，但他对这个问题毫无头绪，你能帮帮他解决这个问题吗？拜托了，牛老师！
输入描述:
输入一个整数n，2 <= n <= 106。
输出描述:
输出一个整数，表示 f(n) 的值。
示例1
输入
18
输出
9
说明
18可以分解成 1 * 18，2 * 9，3 * 6，显然 3 + 6 = 9是最优的(18 = 2 * 3 * 3 由于有重复值所以无法得到)。
示例2
输入
3
输出
4
说明
3可以分解成1 * 3(因数个数必须大于1)，所以答案为4。
思路
直接暴搜，记录出现的因数。
#include<bits/stdc++.h> using namespace std; int n,minn; int t[1000005]; void dfs(int x,int sum){ if(!t[x]&&sum){ minn=min(sum+x,minn); } for(int i=2;i<sqrt(x);i++){ if(x%i==0&&!t[i]){ t[i]++; dfs(x/i,sum+i); t[i]--; } } } int main(){ cin>>n; minn=n+1; dfs(n,0); cout<<minn<<endl; return 0; }