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

mathe

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个解:
[8, 7, 6, 5, 4, 3, 2, 1]
[9, 7, 5, 4, 4, 4, 2, 1]
[10, 7, 4, 4, 4, 3, 3, 1]
[10, 7, 6, 4, 3, 2, 2, 2]

gxqcn

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

mathe

呵呵，本来想用C写， 不过先试用了一下Pari/Gp，发现已经很快了。

1. vf(N)=
   
2. {
   
3.     a=vector(N);
   
4.     P=N!;
   
5.     S=(N*(N+1))/2;
   
6.     s=0;p=P;
   
7.     search(1,N);
   
8. }
   
9. 
   
10. search(step, total)=
    
11. {
    
12.     local(v,c);
    
13.     v=divisors(p);
    
14.     for(u=1,length(v),
    
15.         c=v[u];
    
16.         if(c+s>S,break());
    
17.         if(step>1&&c>a[step-1],break());
    
18.         a[step]=c;
    
19.         s=s+c;
    
20.         p=p/c;
    
21.         if(step<total,
    
22.              search(step+1,total),
    
23.              if(s==S&&p==1,print(a)));
    
24.         p=p*c;
    
25.         s=s-c;
    
26.     )
    
27. }

复制代码

(11:12) gp > vf(7)
[7, 6, 5, 4, 3, 2, 1]
(11:12) gp > vf(8)
[8, 7, 6, 5, 4, 3, 2, 1]
[9, 7, 5, 4, 4, 4, 2, 1]
[10, 7, 4, 4, 4, 3, 3, 1]
[10, 7, 6, 4, 3, 2, 2, 2]
所以N=8的时候分解已经不唯一了。不过N=7只有唯一分解
[8,6,3]~[9,4,4]

gxqcn

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

mathe

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

mathe

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

gxqcn

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

mathe

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

mathe

用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

题目都还没看懂，。，