拜托了,牛老师

题目大意:

给定一个数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);
}

https://blog.csdn.net/s260127ljy/article/details/108233142