= 1! * 2! * 3! * 4! * 5! * 6! * ...

= (1! * 2!) * (3! * 4!) * (5! * 6!) * ...

= (1! * 1! * 2) * (3! * 3! * 4) * (5! * 5! * 6) * ...

= 2 * 4 * 6 * ...

= 2 * (1 * 2 * 3 * ...)

当n是偶数时

答案 = 2! * (n/2)!

当n是奇数时

答案 = 2! * (n/2)! * n!

所以最多只要删3个就可以了

至于2!、(n/2)！、n!能否合并或缩小，本若菜不会，看了楼下几位神犇的方法，觉得是不是存在其他情况，或n>500以后是否存在其他情况？比如，(a!)*(b!)->(c!)*(d!)，或者a!等价于b!但是b比a小

于是，就压缩了1! ... n!的每个素数奇偶情况的01表，然后map搜了一下，就过了

额，迭代加深还真过了。
不会推理的我表示震惊。
```c++
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int INF = 2147483647;
const int preme[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503};

struct An
{
char num[300];
int bigest;
An()
{
memset(num,0,sizeof(num));
bigest=0;
}
An operator*(int a) const
{
An temp=*this;
for(int i=0;;i++)
{
if(a==1) break;
while(a%preme[i]==0)
{
temp.num[i]++;
a/=preme[i];
temp.bigest=max(bigest,i);
}
}
return temp;
}
An operator+(const An &a) const
{
An temp=*this;
temp.bigest=max(bigest,a.bigest);
for(int i=0;i<=temp.bigest;i++)
temp.num[i]+=a.num[i];
return temp;
}
bool is_twice() const
{
for(int i=0;i<=bigest;i++)
if(num[i]%2) return false;
return true;
}
};

An all,jxig[600];
int n,del[600];

bool dfs(int now,int last,int deled)
{
if(last==0)
{
An temp=all;
for(int i=0;i<deled;i++)
{
for(int j=0;j<=temp.bigest;j++)
temp.num[j]-=jxig[del[i]].num[j];
while(temp.num[temp.bigest]==0) temp.bigest--;
}
return temp.is_twice();
}

for(int i=now;i<=n-last+1;i++)
{
del[deled]=i;
if(dfs(i+1,last-1,deled+1)) return true;
}
return false;
}

int main()
{
scanf("%d",&n);
for(int i=2;i<=n;i++)
{
jxig[i]=jxig[i-1]*i;
all= jxig[i]+all;
}
for(int i=1;i<n;i++)
if(dfs(2,i,0))
{
printf("%d\n",i);
for(int j=0;j<i-1;j++)
printf("%d ",del[j]);
printf("%d\n",del[i-1]);
break;
}
return 0;
}
```

本人无聊，就用数学归纳法证明一下：

（只证明m=4k，其它一样，我格式不规范）

证明：

设 s(m)=1!*2!*...*m!

当k=1 时

s(4k)/(2k!)=144 成立！

设n=k 时成立

则s(4k)/(2k!)为平方数

只要n=k+1成立就行了。

s（4（k+1)）/（2（k+1)!)

=s(4k)*(4k+1)!*(4k+2)!(4k+3)!*(4k+4)!/(2k!*(2k+1)(2k+2))

=s(4k)/(2k!) * ((4k)!)^4* (4k+1)^4 *(4k+2)^3 *

(4k+3)^2 *(4k+4)^1 /( (2k+1)(2k+2))

注意到前面几项都为平方数

则只要 (4k+2)^3 *(4k+3)^2 (4k+4)^1 /( (2k+1)(2k+2))为平方数

则只要（4k+2）(4k+4)/( (2k+1)(2k+2))为平方数

显然为4 是平方数。

得证！

。。搜索无果。。

决定使用题解那个构造的方法。别BS我。。

---|---|---|---|---|--悲剧的分割线---|---|---|---|---|---|---|-

=.= 经过N次提交。终于AC了。

错误如下。

1.浮点问题。不多说O.O

2.构造法做到第三种合并时忘记判断是否有2！

｛以下第三种合并

3、当解中有2!和k!时（当2k是完全平方数）

2!*k!==>(k-1)!

相当于在结果中除上一个值为2k的完全平方数

｝

3.做第二种合并时没判断（k+1）是否(k+1)!

相当于在结果中乘上一个值为(k+1)/2的完全平方数

｝

4.引自boyzkk

小心n=1,2,3

---|---|---|---|---|---|华丽的分割线---|---|---|---|---|---|---|--

第250道AC。。

250/694(36%)

---|---|---|---|---|--最后的分割线---|---|---|---|---|---|---|---|

本来准备弄成第100AC的。最后决定还是留给后人吧

^.^

Flag 　　Accepted

题号 　　P1158

类型(?) 　　搜索

通过 　　98人

提交 　　383次

通过率 　　26%

难度 　　3

编译通过...

├ 测试数据 01：答案正确... 25ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 166ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 103ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：294ms

迭代加深搜索 最多3层...

时间好囧~~~~~~~第96个

其实搜索照样秒的，DFS，限定层数

只要一搜到就输出

搜吧

不会推.......

膜拜ipip2005&AlNo3

Orz 膜拜众神牛……

我推了好长时间才推出来，既然ipip2005神牛已经把方法讲了，我就讲一下如何推导

---|---|---|---|---|---|---|---|--华丽丽的分割线---|---|---|---|---|---|---|---|---|-

大家可以把每四个分为一组，都按照表达式表达出来，看看要删掉哪些因子才能成为完全平方数，然后组合起来，你就会豁然开朗~

---|-注意事项同boyzkk神牛

---|---|---|---|---|---|---|---|以下内容与题解无关---|---|---|---|---|---|---|---|--

ipip2005神牛，你又逃了一天 - - 在家逍遥撒~

第88ACer

在12：34：56 07/08/09这个神圣的时刻，成功地通出PVZ(详情见P1607)

竟然打了表才AC 晕

123

谁能把Tango的题解发上来（不要发程序）？

只看ipip2005和AlNo3的题解，不能看明白！

为什么n=4k时就删(2k)!呢？

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

一次AC。

这题目主要是虚张声势，貌似数据规模庞大，其实删的数最大也不超过3个（汗！），数组500000就能过了，放心得BFS吧！！！！！！

改了好半天才过.

Orz诸位神牛

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

小心n=1,2,3

膜拜ipip2005&Tango，鄙视Vijos。我复述一遍ipip2005的解法：

初解n=4k时====删(2k)!n=4k+1时==删(2k)!*(4k+1)!n=4k+2时==删2!*(2k+1)!n=4k+3时==删2!*(2k+1)!*(4k+3)!然后按如下方法把解合并，以缩小解的规模1、(a^2)!==>(a^2-1)!　　正确性显然2、当解中有2!和k!时（当(k+1)/2是完全平方数，也可以说当2(k+1)是完全平方数）2!*k!==>(k+1)!相当于在结果中乘上一个值为(k+1)/2的完全平方数3、当解中有2!和k!时（当2k是完全平方数）2!*k!==>(k-1)!相当于在结果中除上一个值为2k的完全平方数

~~以下内容显然与题解无关~~

Wsxhwyy

Cjfxhlww

Lwwxhcjf

支持Tango，我补充点

n=4k---|-(2k)!

n=4k+1--(2k)!*(4k+1)

n=4k+2--2*(2k+1)!

n=4k+3--2*(2k+1)!*(4k+3)!

再对这些数进行所谓的合并和分解即可

就是对于完全平方数a^2的阶乘，除以该完全平方数得到a^2-1的阶乘，数值就减小。

对于2和k!其中(k+1)/2是完全平方数，那么k!*(k+1)/2也是完全平方数

2和k!合并为(k+1)!

对于2和k!其中2*k是完全平方数，那么(k-1)!*2*k也是完全平方数，把2*k舍掉就成了(k-1)!

此题变得如此简单

Tango 讲解太帅了

佩服佩服!!!

使用n!的展开式，用叠代加深DFS

同下～

注意2,161,323可以变成162,323