POJ 1777

一道好题。

由算术基本定理，知：

那么，对于上式的每个因子值只能是2^M的形式。取第一个式子为例，通过分解因式出（1+p^2）=2^k知，a只能为1.

于是对于p只能是梅森素数。而且每个梅森素数只能出现一次，利用这个就可以求解了，

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int Max=1<<8;

int Mec[10]={(1<<2)-1,(1<<3)-1,(1<<5)-1,(1<<7)-1,(1<<13)-1,(1<<17)-1,(1<<19)-1,(1<<31)-1,0,0};

int vp[10]={2,3,5,7,13,17,19,31,0,0};

int v[150],tans[150],tp;

bool p[Max];

int judge(int t){

	int ans=0;

	for(int i=0;i<8;i++){

		if(t%Mec[i]==0){

			ans|=(1<<i);

			t/=Mec[i];

		}

	}

	if(t==1)

	return ans;

	else return 0;

}

int main(){

	int t;

	while(scanf("%d",&t)!=EOF){

		tp=0;

		int ans=0;

		for(int i=0;i<t;i++)

		scanf("%d",&v[i]);

		memset(p,false,sizeof(p));

		p[0]=true;

		for(int i=0;i<t;i++){

			int tmp=judge(v[i]);

			if(tmp){

				p[tmp]=true;

				tans[tp++]=tmp;

			}

		}

		for(int i=0;i<tp;i++){

			for(int k=0;k<Max;k++){

				if(p[k]){

					if(!(k&tans[i]))

					p[k|tans[i]]=true;

				}

			}

		}

		int e;

		for(int i=Max-1;i>=0;i--)

			if(p[i]){

				int c=0;

				for(int k=0;k<8;k++){

					e=(1<<k);

					if(e&i)

						c+=vp[k];

				}

				ans=max(ans,c);

			}

		if(!ans){

			printf("NO\n");

			continue;

		}

		printf("%d\n",ans);

	}

	return 0;

}