Любое натуральное число можно представить в виде суммы нескольких последовательных натуральных чисел. Например, число 25 можно представить в виде суммы из одного (25), двух (12+13) или пяти (3+4+5+6+7) чисел. Требуется написать программу, которая определит максимальное количество чисел в таком разложении. Технические требования: ограничение во времени тестирования: по 1 секунде на один тест.
Формат входных данных
Входной текстовый файл содержит одно натуральное число n (1≤ n ≤ 1000000000).
Формат выходных данных
Выходной текстовый файл должен содержать одно натуральное число – максимальное количество чисел в разложении числа на сумму последовательных натуральных чисел.
Желательно С++
Логистинг задачи:
var i,n,max,d:LongInt;
x1,x2:Real;
begin
max:=1;
Read(n);
for i:=1 to n div 2 do
begin
d:=sqr(2*i-1)+8*n;
if d<0 then Continue;
x1:=((1-2*i)-sqrt(d))/2;
x2:=((1-2*i)+sqrt(d))/2;
if (frac(x1)=0) and (x1>max) then
begin
max:=Round(x1);
Break;
end;
if (frac(x2)=0) and (x2>max) then
begin
max:=Round(x2);
Break;
end;
end;
Writeln(max);
end.
Листинг программы:
var n, s: longint;
begin
readln(s);
s := 2 * s; {лучше s := s shl 1;}
n := trunc(sqrt(s)); {можно, как планировалось, n := trunc(sqrt(s + 0.25) - 0.5);}
while n > 1 do
if (s mod n = 0) and odd(s div n - n)
then break
else dec(n);
writeln(n)
end.