主题：[原创]最大约数和
abcwuhang
[专家分：1840] 发布于 2007-07-12 15:52:00
问题描述:
选取和不超过S的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。
输入数据:输入一个正整数S。
输出数据:输出最大的约数之和。
样例输入
11
样例输出
9
样例说明:取数字4和6，可以得到最大值(1+2)+(1+2+3)=9。
时间限制:各测试点1秒
回复列表 （共13个回复）
沙发
Matodied [专家分：7560] 发布于 2007-07-12 20:54:00
显然必须选择约数尽可能多的数。
由于总和不超过S，因此最大的约数不能超过TRUNC（S/2）。
还要考虑一个重要的性质：
两个数的和一定，它们的差越大，积越小。
因此只要取最大的数（TRUNC（S/2））和2的积，同时保证这个最大的数的约数尽可能多。
板凳
abcwuhang [专家分：1840] 发布于 2007-07-13 12:26:00
请讲明原理,感觉看起来糊里糊涂...~真晕!!?~~~~
(PS:S未知!问题:如何求S!)
3 楼
cmy28 [专家分：380] 发布于 2007-07-13 13:55:00
我也看不懂耶~~[em8][em8]
4 楼
abcwuhang [专家分：1840] 发布于 2007-07-13 14:26:00
XXXXXXX...~~
5 楼
迷路的天使 [专家分：1340] 发布于 2007-11-21 17:56:00
看不懂`~~~~~```
6 楼
shisutianxia [专家分：630] 发布于 2007-11-25 08:42:00
我的解答，大家看看
program solve;
var t,n,m:longint;
function tot(n:longint):longint;
var i,s:longint;
begin
s:=1;
if trunc(sqrt(n))=sqrt(n) then s:=s-trunc(sqrt(n));
for i:=2 to trunc(sqrt(n)) do
if (n mod i)=0 then s:=s+i+(n div i);
tot:=s;
end;
begin
readln(n);
m:=n mod 6;
t:=tot(n-m);
if (m>1)and(m<=3) then t:=t+1;
if (m>=4)and(m<=5) then t:=t+3;
writeln(t);
end.
7 楼
shisutianxia [专家分：630] 发布于 2007-11-25 08:49:00
是否可以证明，对6M+D,是否可以证明(6M，及D可取最大可约数)的约数和+是最大的呢？
6M，----1，2，3，M，2M，3M
6M+1，
6M+2，---1，2，3M+1
6M+3，---1，3，2M+1
6M+4，---1，2，3M+2
6M+5；
8 楼
shisutianxia [专家分：630] 发布于 2007-11-25 08:54:00
如果可以证明一个数(6M+D)取得最大约数和时,一定是两个数,且其中一个数是6M到6M+D之间那就好办
是否成立呢????THINKING-----------------
9 楼
shisutianxia [专家分：630] 发布于 2007-11-26 12:30:00
不好意思，错了，应该是这样
n1*m1!+n2*m2!+....m1要尽量大，然后n1要尽量大，再M2类似，N2类似。。。。这样处理就可以得出
查分得几个数，再求约数和
10 楼
shisutianxia [专家分：630] 发布于 2007-11-29 12:41:00
我又想了一下，应符合两个原则1.约数相异2.约数要多。那可以这样做
用ZHI数组保存质数ZHI[1]：=2，ZHI[2]：=3.......
对于S，
T：=ZHI[1]*ZHI[2]*....ZHI[N]，刚好T*ZHI[N+1]>S,再T*ZHI[1]*....ZHI[M]刚好ZHI[M+1]*T>S,
重复，直到T不能再乘任何质数，T为要求的拆分的第一个数，类似可的第二个数，第三个...
再把每个数的约数加起来就是所要求得结果，等下我给出程序来，大家看看
我来回复
您所在位置：