Дистанционная подготовка: Программка
Программка
от ar vrt - Воскресенье 19 Июнь 2011, 16:50
147. Алгоритм Евклида
  Почему програма
var a,b,i,c:integer;
begin
read(a,b);
for i := 1 to a do
if (a mod i = 0) and (b mod i = 0) then c := i;
writeln(c);
end.
не работает.
Re: Программка
от Peter Cherepanov - Понедельник 20 Июнь 2011, 00:56
  Потому что это не алгоритм Евклида.

Сложность предложенной программы равна O(a).
При максимальных значениях параметров программа
выполняет 2e9 делений, что не может быть сделано
за одну секунду.

Сложность алгоритма Евклида равна O(log(min(a,b))).
Re: Программка
от Роман Жижнов - Среда 11 Декабрь 2013, 14:44
  почему программа
var q,w:longint;
begin
read(q,w);
while qw do begin
if q>w then q:=q-w
else w:=w-q
end;
write(q)
end.
71 и 72 тесты не проходят по времени
Re: Программка
от Виктор Терещук - Среда 11 Декабрь 2013, 22:05
  Потому что, например, для чисел 2*10^9 и 2 она будет работать слишком долго.
Здесь надо разобраться, как вместо вычитания использовать деление.