Question

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

Answer 1

Ответ:

program abc;

var m,o,k:int64;

begin

  readLn(m);

  o:=2000000000;

  for i:integer:=trunc(sqrt(m))+1 downto 1 do

     if (o>m div sqr(i)) and (m mod sqr(i) = 0) then

     begin

        o:=m div sqr(i);

        k:=sqr(i);

     end;

  writeLn(k);

end.

Объяснение:

Answer 2

Для решения данной задачи можно использовать следующий подход:

1. Начнем с нахождения квадратного корня числа M. Округлим результат вниз до целого числа. Пусть это число будет S.

2. Проверим, является ли S точным квадратом. Если S^2 равно M, то S будет максимально возможным размером полка. В этом случае выводим S и завершаем программу.

3. Если S^2 не равно M, это означает, что M не является точным квадратом. Нам нужно найти наибольшее возможное число X, такое что X^2 не превышает M.

4. Ищем X, начиная с S и уменьшая его на 1 до тех пор, пока X^2 не станет меньше или равно M. Когда найдено такое значение X, выводим его как максимально возможный размер полка.

Ниже приведена реализация данного алгоритма на языке Python:

pythonCopy code
import math

M = int(input())

S = int(math.sqrt(M))

if S * S == M:
    print(S)
else:
    X = S
    while X > 0:
        if X * X <= M:
            print(X)
            break
        X -= 1

Для данного примера с вводом 180, программа выведет:

Copy code
36

Таким образом, максимально возможный размер полка равен 36.