题意：
给n张卡片，每张卡片上面有一个数，卡片的值取决于上面数字符合的条件：
1、这个数字是质数
2、其因子的数量是质数
3、其所有因子的和是质数
4、所有因子的乘积是一个平方数
符合几条，卡片的值就是多少。
给n种卡片，每种卡片上面数字是a，一共有b张。从中取k张，问如何取值最大。
还有一个规则是，要是取的所有k张卡片都不符合其中的某一条，则可加上该条规则对应的一个分数。
需要的知识点：
1、质数打表
2、求一个数的因子
3、二分快速幂
解题思路：
1、首先要把每张卡片对应的值求出来
求出该数字的质因子及其个数，一个个判断条件。
需要注意的是，题目问的是所有因子的数量、和、乘积是否是质数。
我们求的是其质数因子的数量，第一个条件比较简单。
要满足第二个条件，该数字只可能有一个质因子。判断其个数+1是不是质数就可以了。
第三个条件，也必须只含一个素因子p^k.然后求1+p^1+p^2+..+p^k .判断是不是素数。
具体分析、证明，点这个博客里面有。。
2、是否存在都不符合某些条件的情况以加分
这里就直接枚举1<<4种情况（每一位代表该位代表的条件是否符合）
先把所有卡片按已有的得分排序，从得分大的到得分小的符合条件的取
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define ll __int64
using namespace std;
struct node
{
int a,b,score,s;
}num[1010];
bool prime[1000010];
int p[1000010],factor[100][2],prcnt;
int init()
{
int i,j,cnt;
memset(prime,true,sizeof prime);
prime[0]=prime[1]=0;
for(i=2;i<1000010;i++)
{
if(!prime[i]) continue;
for(j=2;i*j<1000010;j++)
prime[i*j]=0;
}
for(i=2,prcnt=0;i<1000010;i++)
{
if(prime[i])//把所有质数按顺序存下来
p[prcnt++]=i;
}
}
int getf(int x)
{
int i,tmp=x,facnt=0;
for(i=0;p[i]<=tmp/p[i];i++)//枚举可能的质因子（当然是质数）
{
factor[facnt][1]=0;//初始化 //[0]存质因子本身 [1]存该质因子个数
if(tmp%p[i]==0)
{
factor[facnt][0]=p[i];
while(tmp%p[i]==0)
{
factor[facnt][1]++;
tmp/=p[i];
}
facnt++;
}
}
if(tmp!=1)//一个质因子都没有找到 就只有自己咯
{
factor[facnt][0]=tmp;
factor[facnt++][1]=1;
}
return facnt;
}
ll Pow(ll a,ll b)//二分的思想求幂
{
ll ans = 1;
while(b){
if(b&1) ans=ans*a;
a=a*a;
b>>=1;
}
return ans;
}
int sum(int x,int y)
{
if(x==0) return 0;
if(y==0) return 1;
if(y&1) return (1+Pow(x,y/2+1))*sum(x,y/2);
else return (1+Pow(x,y/2+1))*sum(x,y/2-1)+Pow(x,y/2);
}
void check(int id)
{
int facnt=getf(num[id].a);
num[id].s=0;//s的二进制共四位表示四种条件 1或0表示是否满足该条件
//第一个条件 判断是否是质数
if(facnt==1&&factor[0][1]==1)
num[id].s |=(1<<0);
//第二个 因子（不等同于质数因子）个数是质数
if(facnt==1&&prime[factor[0][1]+1])
num[id].s|=(1<<1);
//第三个 因子和是质数
if(facnt==1&& prime[sum(factor[0][0],factor[0][1])])
num[id].s|=(1<<2);
//第四个 因子乘积为平方数
int i,j,flag=1;
for(i=0;i<facnt;i++)
{
ll tmp=(factor[i][1]+1)*factor[i][1]/2;
for(j=0;j<facnt;j++)
{
if(i!=j)
tmp=tmp*(factor[j][1]+1);
}
if(tmp%2!=0)
{
flag=0;
break;
}
}
if(flag) num[id].s|=(1<<3);
num[id].score=0;
for(i=0;i<4;i++)
{
if(num[id].s&(1<<i))
num[id].score++;
}
}
bool cmp(node a,node b)//按分数大小排序
{
return a.score>b.score;
}
int main()
{
int t,n,k,i,ii,j,ans,res,tmp,w[5];
init();
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&k);
for(i=0;i<n;i++)
{
scanf("%d%d",&num[i].a,&num[i].b);
check(i);
if(i!=0) putchar(‘ ‘);
printf("%d",num[i].score);
}
puts("");
for(i=0;i<4;i++)
scanf("%d",&w[i]);
sort(num,num+n,cmp);//按得分大小排序
ans=-100000000;
for(i=0;i<(1<<4);i++)
{
res=k;//记现在还要取多少张牌
tmp=0;//现在这种情况的总得分
ii=0;//取了的卡片占了哪些条件//不知道为什么一定要有这个量 直接枚举i不行吗
for(j=0;j<n;j++)
{
if(!(num[j].s&i))//符合i条件的就取
{
if(res==0) break;
ii|=num[j].s;
tmp+=(num[j].score*min(res,num[j].b));
res-=min(res,num[j].b);
if(res==0) break;
}
}
if(res!=0) continue;
for(j=0;j<4;j++)
{
if((ii&(1<<j))==0)
tmp+=w[j];
}
ans=max(ans,tmp);
}
printf("%d\n",ans);
}
return 0;
}
原文：http://blog.csdn.net/u011032846/article/details/21551955