33,010
社区成员
发帖
与我相关
我的任务
分享连续自然数和的序列
有些自然数可以表示为几个连续的自然数之和，例如
3 = 1+2
9 = 4+5
9 = 2+3+4
现在想知道在64位正整数范围内，子序列数目最多的数是哪一个？例如9就有两种子序列表示，它的子序列数目为2，这个问题能否用数学而不是蛮力的方法计算出来呢？
3 = 1+2
9 = 4+5
9 = 2+3+4
现在想知道在64位正整数范围内，子序列数目最多的数是哪一个？例如9就有两种子序列表示，它的子序列数目为2，这个问题能否用数学而不是蛮力的方法计算出来呢？
...全文
请发表友善的回复…
发表回复
knowledge_Is_Life 2008-05-01
- 打赏
- 举报
等待牛人来答.
boxer_tony 2008-04-17
- 打赏
- 举报
抱歉，我弄错了。
还有：
45=22+23
45=14+15+16
45=45
还有：
45=22+23
45=14+15+16
45=45
boxer_tony 2008-04-17
- 打赏
- 举报
3楼的解法存在问题：
比如n=45 = 3^2 * 5, 照你的解法它有(2+1)*(1+1) = 6个子序列
可它实际上只有3个子序列：
45 = 1+2...+9
45 = 5+6+...+10
45 = 7+8+...+11
比如n=45 = 3^2 * 5, 照你的解法它有(2+1)*(1+1) = 6个子序列
可它实际上只有3个子序列：
45 = 1+2...+9
45 = 5+6+...+10
45 = 7+8+...+11
freeCodeSunny 2008-04-15
- 打赏
- 举报
3L n=2^k2 * 3^k3 * 5^k5 * ... * n^kn. 后面的数因为有个限制条件吧!就是一定是素数,
freeCodeSunny 2008-04-15
- 打赏
- 举报
这个好象那一年的公务员考试就有这样的题,在百度一搜就可以了,有具体解法,
xdspower 2008-04-15
- 打赏
- 举报
这道题因为要求最多连续子序列的和为X
设某个数的最多子序列为N，则一定存在
int(X/N) 记为X整除N的值
int(X/N)-int(N/2)>0
N>0且为整数
则这样可以确定N的上限
比如对于9，有
N=2
则
int(9/2)=4
int(2/2)=1
4-1=3>0
N=3
则
int(9/3)=3
int(3/2)=1
3-1=2>0
N=4
则
int(9/4)=2
int(4/2)=2
2-2=0 这样可以比较快的确认N的最大范围
设某个数的最多子序列为N，则一定存在
int(X/N) 记为X整除N的值
int(X/N)-int(N/2)>0
N>0且为整数
则这样可以确定N的上限
比如对于9，有
N=2
则
int(9/2)=4
int(2/2)=1
4-1=3>0
N=3
则
int(9/3)=3
int(3/2)=1
3-1=2>0
N=4
则
int(9/4)=2
int(4/2)=2
2-2=0 这样可以比较快的确认N的最大范围
medie2005 2008-04-14
- 打赏
- 举报
在64位正整数范围内，子序列数目最多的数是13835020108241056725，它可表示为：3^3*5^2*7*11*13*17*19*23*29*31*37*41*43*47.
它可写成的子序列数目是4*3*2^12=3*2^14=49152个。
它可写成的子序列数目是4*3*2^12=3*2^14=49152个。
fosjos 2008-04-08
- 打赏
- 举报
设M=2^k2 * 3^k3 * 5^k5 * ... * n^kn
由于偶数长度序列平均值必须是n+0.5，最多只能有一个序列，长度2*2^k2
例如9=2*4.5 10=4*2.5
所以k2取最小0, M=3^k3 * 5^k5 * ... * n^kn是奇数
一种长度，最多只能有一个序列
设M=M1*M2，长度M1，序列首项M2-(M1-1)/2>=1 => 2*M2-M1>=1
设M1<=M2，长度M2序列一定存在，长度M1的序列暂无结论
所以一种算法是考虑因数多样性：
M=3*5*7*11*...*N * 3*5*7*11*...
但只是较多，不知是不是最多
由于偶数长度序列平均值必须是n+0.5，最多只能有一个序列，长度2*2^k2
例如9=2*4.5 10=4*2.5
所以k2取最小0, M=3^k3 * 5^k5 * ... * n^kn是奇数
一种长度，最多只能有一个序列
设M=M1*M2，长度M1，序列首项M2-(M1-1)/2>=1 => 2*M2-M1>=1
设M1<=M2，长度M2序列一定存在，长度M1的序列暂无结论
所以一种算法是考虑因数多样性：
M=3*5*7*11*...*N * 3*5*7*11*...
但只是较多，不知是不是最多
medie2005 2008-04-08
- 打赏
- 举报
设n写成的连续的自然数以a开头，以b结尾。则，长度为b-a+1.
由求和公式，得：(b-a+1)*(b+a)/2=n
=> (b-a+1)*(b+a)=2n
因为b-a和a+b是同奇偶的，于是(b-a+1)和(b+a)一奇一偶。
若n=2^k2 * 3^k3 * 5^k5 * ... * n^kn.
于是，n写成连续自然数之和形式的个数是:m=3^k3 * 5^k5 * ... * n^kn的真因子个数。
而3^k3 * 5^k5 * ... * n^kn的因子个数是:(k3+1)*(k4+1)*...*(kn+1).
于是，我们现在只要求在64位正整数范围内，形式为3^k3 * 5^k5 * ... * n^kn（偶数可以不用考虑了）,且(k3+1)*(k4+1)*...*(kn+1)最大的数.
这个问题呢，其实在ACM中经常出现，一些题目称其为“反素数”。
反素数的性质：
性质一:一个反素数的质因子必然是从2开始连续的质数.
性质二:p=2^t1*3^t2*5^t3*7^t4.....必然t1>=t2>=t3>=....
对我们这个题目来说，m=3^k3 * 5^k5 * ... * n^kn，质因子是从3开始，且k3>=k5>=k7>=...>=kn。
对64位整数范围来说，最多只需要14个素数构造:3,5,7,11,13,17,19,23,29,31,37,41,47,51.
这样，我们就可以利用k3>=k5>=k7>=...>=kn这个条件来搜索解了。
具体算法可以用回溯法，附加一些剪枝操作，可以很快出解了。
由求和公式，得：(b-a+1)*(b+a)/2=n
=> (b-a+1)*(b+a)=2n
因为b-a和a+b是同奇偶的，于是(b-a+1)和(b+a)一奇一偶。
若n=2^k2 * 3^k3 * 5^k5 * ... * n^kn.
于是，n写成连续自然数之和形式的个数是:m=3^k3 * 5^k5 * ... * n^kn的真因子个数。
而3^k3 * 5^k5 * ... * n^kn的因子个数是:(k3+1)*(k4+1)*...*(kn+1).
于是，我们现在只要求在64位正整数范围内，形式为3^k3 * 5^k5 * ... * n^kn（偶数可以不用考虑了）,且(k3+1)*(k4+1)*...*(kn+1)最大的数.
这个问题呢，其实在ACM中经常出现，一些题目称其为“反素数”。
反素数的性质：
性质一:一个反素数的质因子必然是从2开始连续的质数.
性质二:p=2^t1*3^t2*5^t3*7^t4.....必然t1>=t2>=t3>=....
对我们这个题目来说，m=3^k3 * 5^k5 * ... * n^kn，质因子是从3开始，且k3>=k5>=k7>=...>=kn。
对64位整数范围来说，最多只需要14个素数构造:3,5,7,11,13,17,19,23,29,31,37,41,47,51.
这样，我们就可以利用k3>=k5>=k7>=...>=kn这个条件来搜索解了。
具体算法可以用回溯法，附加一些剪枝操作，可以很快出解了。
barenx 2008-04-07
- 打赏
- 举报
满足（1~N1）的求和与（1~N2）的求和的差 N2<N1-1,N1不大于S/2的上整
感觉上实在解不定方程
感觉上实在解不定方程
