拜托了,牛老师
题目大意:
给定一个数n,对他进行严格的因数分解,且分解的因数个数要大于1,求这些因数和的最小值。
思路
首先想到的竟然是二分
递归求解,每次将n分成两个数相乘,将其中的一个数进入下一层递归继续求解,另一个数则标记一下不能再使用,在递归的开始求出当前总和并和最小值比较。
Code:
#include<bits/stdc++.h> using namespace std; const int MAXN=2e6+5; int n,ans,t[MAXN]; void f(int x,int sum){ if(sum&&!t[x]) ans=min(ans,sum+x); for(int i=2;i*i<=x;++i) if(x%i==0&&!t[i]&&i!=n/i){ t[i]++; f(x/i,sum+i); t[i]--; } } int main(){ scanf("%d",&n); ans=n+1; f(n,0); printf("%d\n",ans); }