Задача в Паскале!!!! В параде принимают участие M военных. Командование парада решило,...

Question

Задача в Паскале!!!! В параде принимают участие M военных. Командование парада решило, что наиболее эффектное построение военных – в форме квадрата, то есть число участников построения должно быть точным квадратом. Но поскольку число M может не быть точным квадратом, разрешается разбить военных на несколько полков, каждый из которых строится в форме квадрата. Для красоты все полки должны быть одинакового размера, также командование парада хочет, чтобы размер каждого полка был как можно больше. Определите максимально возможный размер полка. Программа получает на вход одно целое положительное число M, не превосходящее 2×10в(9)степени , – количество участников парад. Программа должна вывести одно число – максимально возможный размер полка Ввод:180 Вывод:36

Answer 1

Формально, нужно найти максимальное натуральное N, такое, что существует натуральное k, что M = k * N^2 (N – сторона квадрата, k –количество квадратов), и вывести N^2.

Решаем в лоб: перебираем N от 44721 до 1, если M делится на N^2, выводим N^2. Большие N перебирать бессмысленно, N в квадрате будет слишком большим.

Программа:

var M, N: longint;

begin

 read(M);

 for N := 44721 downto 1 do

   if M mod (N * N) = 0 then

   begin

     write(N * N);

     break;

   end

end.