北京信息科技大学第十一届程序设计竞赛（重现赛）E kotori和素因子

链接：/acm/contest/940/E

来源：牛客网

题目描述

kotori拿到了一些正整数。她决定从每个正整数取出一个素因子。但是，kotori有强迫症，她不允许两个不同的正整数取出相同的素因子。

她想知道，最终所有取出的数的和的最小值是多少？

注：若a%k==0，则称k是a的因子。若一个数有且仅有两个因子，则称其是素数。显然1只有一个因子，不是素数。

打表筛出每个数的质因子，然后深搜求解最小值

#include<bits/stdc++.h>using namespace std;#define PB push_back#define LL long long#define FI first#define SE second#define POP pop_back()#define PII pair<LL,LL>#define PCC pair<char,char>#define endl '\n'#define ls x<<1#define rs x<<1|1#define m(x) a[x].l+a[x].r>>1const int N=1e3+7;const int INF=1e8,mod=1e8;vector<int>v[N];int f[N];int n,a[N];int ans;int b[N];void dfs(int x,int y){if(x>n){ans=min(ans,y);return;}for(int i=0;i<v[a[x]].size();i++){if(!f[v[a[x]][i]]){f[v[a[x]][i]]=1;b[x]=v[a[x]][i];dfs(x+1,y+v[a[x]][i]);f[v[a[x]][i]]=0;}}}int main(){ans=INF;for(int i=2;i<=1000;i++){if(!f[i]){v[i].PB(i);for(int j=i+i;j<=1000;j+=i){v[j].PB(i);f[j]=1;}}}memset(f,0,sizeof(f));cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}dfs(1,0);if(ans==INF)cout<<-1;else cout<<ans;return 0;}