今天是five20巨佬出的一套题目，考得心态爆炸，太弱了只打表拿到了第一题十分。总结一下第一题math
对于一个正整数 n,从 1!、2!、3!、......、n!中至少删去几个阶乘,就能使余下的阶乘的乘积是完全平方数?
输出删去的个数以及删去的阶乘
对于 100%数据 1≤n≤500
这道题看到数据很大，下意识的觉得这是道数论结论题，打表想找规律，没有去仔细推阶乘之间的关系。
这道题需要先证明一个结论才比较容易想清楚。
1.若n为奇数
先去掉n!。剩余为1!*2!*3!……*(n-2)!*(n-1)!
将其两两放一起，则变为(1!^2*2)*(3!^2*4)*(5!^2*6)……[(n-2)!^2*(n-1)]。
将其化简为求积的形式 for i=1 to (n-1)/2 (2i-1)!^2*(2*i)
当其为完全平方数时，则要满足 for i=1 to (n-1)/2 2*i == 2^[(n-1)/2]*[(n-1)/2]!为完全平方数。
若(n-1)/2为奇数，则2^(n-1)/2不为完全平方数，删掉2!
此时不管[(n-1)/2]!为不为完全平方数 最多删去3个阶乘
2.若n为偶数
先不去掉n!。操作如同奇数删后。
综上所述，这道题最多删去三个阶乘！！！
这时候就有很多的算法了，迭代深搜啊什么的。这里写下five20巨佬的状压。
为什么想到用状压呢？因为完全平方数可以写为数的平方或积的平方，而任意一个数都能写成质数的积的形式，将质数压进每一位中，用0，1表示质数目前的奇偶，当整个数为0时，表示每一个质数的个数均为偶数(包括0)，即完全平方数。
可以这样操作可行的原因是奇偶性:奇+奇=偶，奇+偶=奇，偶+偶=偶。可以用^操作。
那么提前预处理，直接把每个数算出为它的质因子以及每个质因子的个数，这样就可以方便地判断除法之后是否为完全平方数了。
因为500以内有98个质数，用压位来表示数值有2^98这么大，爆掉了long long，所以我们用二维数组mask[501][2]，0即前49个质数的状态，1即后49个质数的状态。
下面是five20巨佬的代码
1 /*这题只要知道结论：答案个数小于等于3个。就so easy了，方法很多，可以乱写，我写的状压仅供参考——by 520*/ 2 #include<cstdio> 3 #define N 501 4 typedef long long ll; 5 int n,tot,pri[100]; 6 bool b[N]; 7 ll m,mask[N][2],aim0,aim1; 8 int main() 9 { 10 freopen("math.in","r",stdin); 11 freopen("math.out","w",stdout); 12 scanf("%d",&n); 13 for(int i=2;i<23;i++) 14 if(!b[i])for(int j=i<<1;j<501;j+=i)b[j]=1; //这里b数组是筛法预处理质数，若!b[i]则i为质数，若b[i]则为合数 15 for(int i=2;i<500;i++) if (!b[i]) pri[tot++]=i; //pre数组记录质数，tot为质数个数 16 17 for(int i=2,k;i<=n;i++) 18 { 19 k=i;m=1; 20 for(int j=0;j<50&&pri[j]<=k;j++,m<<=1) /*这里就是统计某个数的质因子,j设定为50是小优化：因为500以内共 21 98个质数，而m最多为2^64-1，所以我折半枚举，先来50次*/ 22 while(k%pri[j]==0){ //解释下m，状压，每个m<<1即代表一个质数 23 k/=pri[j]; 24 mask[i][0]^=m; /*mask[i][0]若为0,则说明i的pre[j]这个质因子的个数为偶数或者没有*/ 25 } 26 m=1; 27 for(int j=50;j<tot&&pri[j]<=k;j++,m<<=1) /*这里的意思同上，只不过两部分都用了m，而m<<1的值只能表示 28 一个质数，所以将两部分隔开，这里就是mask[i][1]啦*/ 29 while(k%pri[j]==0){ 30 k/=pri[j]; 31 mask[i][1]^=m; 32 } 33 mask[i][0]^=mask[i-1][0]; /*这里就是合并该数和上一个数的质因子个数*/ 34 mask[i][1]^=mask[i-1][1]; 35 } 36 37 if(mask[n][0]==0&&mask[n][1]==0) /*若n的质因子个数为偶数，则不需删除任何数*/ 38 { 39 puts("0"); 40 return 0; 41 } 42 43 //上面预处理后，下面直接依次枚举删去1个、2个、3个的情况就OK了 44 45 for(int i=2;i<=n;i++)aim0^=mask[i][0],aim1^=mask[i][1]; /*这里是删去1个的暴力枚举， 46 aim0取出前面50个质因数的压位值，aim1后面的同理*/ 47 for(int i=2;i<=n;i++) 48 if(mask[i][0]==aim0&&mask[i][1]==aim1) /*上面aim0异或出的值即若和mask[i][0]相等， 49 且aim1和后面的相等，则说明删去该数就保证质因子个数为偶数*/ 50 { 51 puts("1"); 52 printf("%d ",i); //所以删去该数 53 return 0; 54 } 55 56 for(int i=2;i<n;i++) /*删去2个数的枚举，直接n方暴力*/ 57 for(int j=i+1;j<=n;j++) 58 if(aim0==(mask[i][0]^mask[j][0])&&aim1==(mask[i][1]^mask[j][1])) //思路和枚举1个的一样 59 { 60 puts("2"); 61 printf("%d %d ",i,j); 62 return 0; 63 } 64 65 for(int i=2;i<n-1;i++) //删去3个数的枚举，n^3暴力，实际是不会超时的，因为最坏情况难以出现 66 for(int j=i+1;j<n;j++) 67 for(int k=j+1;k<=n;k++) 68 if(aim0==(mask[i][0]^mask[j][0]^mask[k][0])&&aim1==(mask[i][1]^mask[j][1]^mask[k][1])) 69 { 70 puts("3"); 71 printf("%d %d %d ",i,j,k); 72 return 0; 73 } 74 }