麓麓学数学（math.cpp）
描述
麓麓不仅玩游戏十分厉害,而且数学也非常好,可是这次他被
一道数学题难住了,于是他来求助身为信息大佬的你来解决这个问
题:对于一个正整数 n,从 1!、2!、3!、......、n!中至少删去几个
阶乘,就能使余下的阶乘的乘积是完全平方数?
格式
输入格式
仅一行,包含一个整数 n(1≤n≤500)。
输出格式
第一行包含一个整数 k,表示最少需要删去的阶乘个数。
接下来一行,从小到大排列的 k 个[1,n]之间的整数,给出删数的方案。注意若方案不止一种,输出方案从小到大排序序列最小一组即可。
样例 1
样例输入 1
5
样例输出 1
2
2 5
限制��֢��ҩ,�еķ�ʸ
各个测试点 1s
对于 100%数据 1≤n≤500
提示
样例说明:去掉 2!和 5!,剩下的 4,3,1 的阶乘乘积为 4!×3!×
1!=144=12^2。
没啥提示,这题考数学。
Solution：
本题考察数学+暴力巧解。
首先很容易想到暴力搜索，直接迭代加深搜索ida*（运气好的话限制深度可以过），但实际上这题如果我们提前预知结论：答案个数不超过3。这样就好做了，考虑对于一个数k，它是不是完全平方数，即它的质因子的个数是否都为偶数。（譬如4,它的质因子只有2且2的个数为偶数，则4是完全平方数）。
那么提前预处理，直接把每个数表示为它的质因子以及每个质因子的个数，这样就可以方便地判断除法之后是否为完全平方数了。
进一步，我们可以直接把每个质因子个数表示为“奇偶”，因为我们并不需要质因子的个数，只需要其奇偶性。（压位用，譬如：某一质因数个数奇+奇=偶，偶+偶=奇，偶+奇=奇）
亲测，其实完全不压位也能过，但是那样代码太短难度直线下降。
证明让520口述。
如果你数学炸天（譬如高一数竟班的鸡哥，他告诉我的结论在vijos上有50分）
详解见代码
代码：
1 /*这题只要知道结论：答案个数小于等于3个。就so easy了，方法很多，可以乱写，我写的状压仅供参考——by 520*/ 2 #include 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\n",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\n",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\n",i,j,k);72 return 0;73 }74 }