hdu 4610 Cards - c++编程基础

题意：

给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 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #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
           
            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