Олимпиадная информатика

Задача «Кошки-мышки»

Несколько кошек съели М мышек, причём все кошки съели по одинаковому (целому) числу мышек и каждая кошка съела больше мышек, чем было кошек. Вам необходимо узнать, сколько было кошек. Если вариантов несколько, необходимо указать их общее число и перечислить все эти варианты.

Формат входного файла input.txt

Входной файл содержит единственное целое число М (2 <= М <=2*10⁹ ) - количество мышек.

Формат выходного файла output.txt

Выходной файл должен содержать слово NO, если задача не имеет решения. В противном случае, первая строка содержит одно число N - количество возможных решений задачи. Во второй строке записаны через пробел N чисел в возрастающем порядке, каждое из которых равно возможному числу кошек.

var
  k, i, n, a, m: longint;
  z: array[0..30000] of longint;

begin
  assign(input, 'input.txt');reset(input);
  assign(output, 'output.txt');rewrite(output);
  read(m);
  k := 0;
  a := 1;
  while a*a <m do
  begin
    if m mod a = 0 then begin
      inc(k);z[K] := a;
    end;
    inc(a);
  end;
  writeln(k);
  for i := 1 to k do
    write(z[i], ' ');
  close(input);
  close(output);
end.





close
 

Разбор задачи №2 "Кошки - мышки"

Формализуем задачу: надо разложить число М на 2 неравных множителя и вывести меньший из них.

Задача решается перебором всех чисел от 1 до квадратного корня из данного числа. Поскольку нужно сначала вывести общее число, то храним результаты в массиве.

Т.к. любое число делится на 1, то задача всегда имеет решение (по условию М больше 1).