Вв параде принимают участие m военных. командование парада решило, что наиболее эффектное построение

Question

Информатика: Вв параде принимают участие m военных. командование парада решило, что наиболее эффектное построение военных – в форме квадрата, то есть число участников построения должно быть точным квадратом. но поскольку число m может не быть точным квадратом, разрешается разбить военных на несколько полков, каждый из которых строится в форме квадрата. для красоты все полки должны быть одинакового размера, также командование парада хочет, чтобы размер каждого полка был как можно больше. определите максимально

mnadezhkin · Answer

Формально, нужно найти максимальное натуральное 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.