二分求调

#include<bits/stdc++.h>
using namespace std;
const int N=70;
int n,sum,now;
int a[N],un[N];
bool use[N];
bool prime(int x){
	if(x<=2)return 1;
	for(int i=1;i*i<=x;i++)
		if(x%i==0)return 0;
	return 1;
}
bool cmp(int x,int y){
	return x>y;
}
bool dfs(int k,int l,int s){
	bool ret=0;
	if(s==now){
		if(k==sum/now)return 1;
		int u=0;
		for(int i=2;i<=n;i++)
			if(!use[i]){u=i;break;}
		use[u]=1;
		ret=dfs(k+1,u,a[u]);
		use[u]=0;
		return ret;
	}
	for(int i=l+1;i<=n;i++){
		if(use[i]||s+a[i]>now)
			continue;
		use[i]=1;
		ret=dfs(k,i,s+a[i]);
		use[i]=0;
		if(ret)return 1;
	}
	return 0;
}
void search(int L,int R){
	if(L>=R){
		printf("%d\n",L);
		exit(0);
	}
	now=(L+R)/2;
	if(sum%now==0&&dfs(1,1,a[1]))search(L,now);
	else search(now+1,R);
	return;
}
signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]),sum+=a[i];
	sort(a+1,a+n+1,cmp);
	use[1]=1;
	if(prime(sum))printf("%d\n",sum);
	else search(1,sum);
    return 0;
}