题解

26 条题解

  • 2
    @ 2012-07-15 15:50:15

    = 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搜了一下,就过了

  • 1
    @ 2016-06-14 21:00:08

    额,迭代加深还真过了。
    不会推理的我表示震惊。
    ```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;
    }
    ```

  • 1
    @ 2009-11-06 19:39:29

    本人无聊,就用数学归纳法证明一下:

    (只证明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 是平方数。

    得证!

  • 0
    @ 2009-11-06 19:28:56

    。。搜索无果。。

    决定使用题解那个构造的方法。别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

  • 0
    @ 2009-11-05 19:26:50

    编译通过...

    ├ 测试数据 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个

  • 0
    @ 2009-10-11 16:51:45

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

    只要一搜到就输出

  • 0
    @ 2009-08-28 12:53:40

    搜吧

    不会推.......

  • 0
    @ 2009-08-07 14:45:13

    膜拜ipip2005&AlNo3

  • 0
    @ 2009-08-07 15:33:49

    Orz 膜拜众神牛……

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

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

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

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

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

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

    第88ACer

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

  • 0
    @ 2009-08-07 10:58:17

    竟然打了表才AC 晕

  • 0
    @ 2009-06-30 08:53:33

    123

  • 0
    @ 2009-06-08 13:13:56

    谁能把Tango的题解发上来(不要发程序)?

    只看ipip2005和AlNo3的题解,不能看明白!

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

  • 0
    @ 2009-06-04 12:57:50

    编译通过...

    ├ 测试数据 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吧!!!!!!

  • 0
    @ 2009-04-06 15:29:20

    改了好半天才过.

    Orz诸位神牛

  • 0
    @ 2009-03-28 15:30:01

    编译通过...

    ├ 测试数据 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

  • 0
    @ 2008-09-18 18:44:52

    膜拜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

  • 0
    @ 2008-08-12 16:22:01

    支持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)!

    此题变得如此简单

  • 0
    @ 2007-11-15 14:21:14

    Tango 讲解太帅了

    佩服佩服!!!

  • 0
    @ 2006-10-28 15:25:00

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

  • 0
    @ 2006-10-14 20:15:46

    同下~

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

信息

ID
1158
难度
6
分类
其他 | 数学 点击显示
标签
(无)
递交数
310
已通过
91
通过率
29%
被复制
4
上传者