主题：[原创]最大约数和
abcwuhang
[专家分：1840] 发布于 2007-07-12 15:52:00
问题描述:
选取和不超过S的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。
输入数据:输入一个正整数S。
输出数据:输出最大的约数之和。
样例输入
11
样例输出
9
样例说明:取数字4和6，可以得到最大值(1+2)+(1+2+3)=9。
时间限制:各测试点1秒
回复列表 （共13个回复）
11 楼
shisutianxia [专家分：630] 发布于 2007-11-29 12:57:00
程序如下，怎样？对吧！~当然我没用高精算法，LONGINT也可以吧！如果有问题，希望大家帮忙，谢谢！
program zuidayueshu;
var zhi:array[2..97]of integer;
t,m,n,s,i,j,x:longint;w:set of 2..97;
function qiuhe(n:longint):longint;
var s,i: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;
qiuhe:=s;
end;
begin
readln(s);
w:=[2..97];x:=2;i:=0;
repeat
while not (x in w) do
x:=x+1;
inc(i);zhi[i]:=x;j:=x;
while j in w do
begin
w:=w-[j];
j:=j+x;
end;
until w=[];
n:=0;
repeat
m:=1;
while (s-m*2)>0 do
begin
t:=1;i:=0;
while (s-t*m*(zhi[i+1]))>0 do
begin
inc(i);
t:=t*zhi[i];
end;
m:=t*m;
end;
writeln('-->',m);s:=s-m;
n:=n+qiuhe(m)
until s<=1;
write('<',n,'>');
end.
12 楼
shisutianxia [专家分：630] 发布于 2007-12-06 10:59:00
该给出正确答案了吧！！！！！！！！谢谢了
13 楼
augur_1990 [专家分：0] 发布于 2008-10-24 08:15:00
应该用01背包的思想做吧。
用dp可以大大的提高效率！
我来回复
您所在位置：