Шифр Цезаря(#1003) MIME64(#1005)
#1004

Задача g6_1004: Равновеликие прямоугольники.
Прямоугольники, площади которых равны, называются равновеликими. Написать программу, находящую все возможные целочисленные стороны равновеликих прямоугольников заданной площади. Одинаковые прямоугольники, получающиеся заменой сторон, печатать не надо.
Входные данные:
Площадь четырехугольника (1<=n<=50000).
Выходные данные:
Стороны четырехугольника (A*B)
Пример входных данных:
12
Пример выходных данных:
1*12
2*6
3*4
Решение g6_1004:
Попробуем упростить задачу. Разберемся, что такое площадь прямоугольника. Площадь прямоугольника - произведение длин двух прилежащих сторон. Т.е. задачу можно представить как нахождение всех пар множителей, дающих заданный результат.
Рассмотрим алгоритм эффективного поиска множителей данного числа. (Кстати, эта задача была на одной из олимпиад несколько лет назад)
Мы будем искать одновременно два сопряженных множителя, т.е. множителя, которые при перемножении дают искомое число.
Код программы:

    MaxF := trunc(sqrt(N)); {Первый множитель данного числа не может быть больше корня из этого числа, в то время как сопряженный с ним множитель всегда не меньше этого корня}
    For F := 1 to MaxF do
      If N mod F = 0 then Writeln (F, N div F);

Вот и все! Для примера я приведу авторское решение:

    {Равновеликие прямоугольники. Решение А.Никитина, Самара }
    program equrectangle;
    var p:word; {переменная для площади}

    procedure find_and_print_side(a,b:word);
    begin
        if (a<=b) then begin
           if (a*b=p) then writeln(a,'*',b);
           inc(a); find_and_print_side(a,p div a);
        end;
    end;

    begin { основная программа }
       assign(input,'square.in'); reset(input); readln(p); close(input);
       assign(output,'square.out'); rewrite(output);
       find_and_print_side(1,p);
       close(output);
    end.

По моему мнению, оно неэффективное. Для этого я проделал небольшой эксперимент:
1) Заменил ограничение на N<=1000000000.
2) Исправил в авторском решении тип переменных с word на longint.
На тесте 98765432 я не дождался, пока программа найдет ответ, а если ввести какое-нибудь большое простое число, то она будет проводить n итераций, в то время как моя программа независимо от числа производит sqrt(n) операций. Ура мне :)
Скачать тесты к задаче
Наверх