mathe 发表于 2010-3-5 11:00:30

[转载]阶乘和积分解问题

http://tieba.baidu.com/f?kz=723550649
n个正整数，可以有相同的，他们和是1到n所有整数的和，积是1到n所有整数的积，问n最大能到多少，使得这n个数只能是1到n所有整数

链接中已经给出:
1*6*7*10=2*3*5*14
1+6+7+10=2+3+5+14
所以余下工作量很小了。
谁写个程序穷举一下？

------------------------
扩展问题:
求N个正整数（可以存在相等的数），要求和为${N(N+1)}/2$,积为$N!$的解的数目
如N=8,有4个解:



gxqcn 发表于 2010-3-5 11:15:15

题目读的很费解。
比如说，LZ所举例子中对应的n是多少？

mathe 发表于 2010-3-5 11:15:28

呵呵，本来想用C写， 不过先试用了一下Pari/Gp，发现已经很快了。vf(N)=
{
    a=vector(N);
    P=N!;
    S=(N*(N+1))/2;
    s=0;p=P;
    search(1,N);
}

search(step, total)=
{
    local(v,c);
    v=divisors(p);
    for(u=1,length(v),
      c=v;
      if(c+s>S,break());
      if(step>1&&c>a,break());
      a=c;
      s=s+c;
      p=p/c;
      if(step<total,
             search(step+1,total),
             if(s==S&&p==1,print(a)));
      p=p*c;
      s=s-c;
    )
}(11:12) gp > vf(7)

(11:12) gp > vf(8)




所以N=8的时候分解已经不唯一了。不过N=7只有唯一分解
~

gxqcn 发表于 2010-3-5 11:29:32

是不是找两组相同数目的正整数，满足和相等且积亦相等？
如果是这样的话，n可以任意大。

mathe 发表于 2010-3-5 11:32:57

其中一组指定是1~N这N个数，要求不存在另外一组

mathe 发表于 2010-3-5 11:39:19

我们可以改进一下难度，改为计算对于每个N分别有多少个解。
相当于求N个正整数（可以存在相等的数），要求和为${N*(N+1)}/2$,积为$N!$的解的数目

gxqcn 发表于 2010-3-5 11:39:42

为什么“要求不存在另外一组”？

mathe 发表于 2010-3-5 11:42:57

1～n本身这一组总是存在的呀。

mathe 发表于 2010-3-5 11:45:59

用Pari/Gp计算出来的参考结果:
(11:41) gp > vf(8)
%9 = 4
(11:42) gp > vf(9)
%10 = 12
(11:42) gp > vf(10)
%11 = 30
(11:42) gp > vf(11)
%12 = 31
(11:42) gp > vf(12)
%13 = 112
不过再计算下去有点难度了

wayne 发表于 2010-3-5 11:55:13

题目都还没看懂，。，:L
页: [1] 2
查看完整版本: [转载]阶乘和积分解问题