Анализ на задача nod

Тази задача ни затруднява с доста интересно нещо - кара ни да пишем решението ни в машинен код. Реално задачата ни логически ни представя пред друго предизвикателство - трябва да намерим НОД на две числа само с операции плюс и минус. Нека преминем към решенията:

Подзадача 1: а=1
В този случай единственият делител на а е едно, а както знаем всяко естествено число се дели на едно, затова просто трябва да върнем като отговор 1.

Подзадача 2: a, b<=5
Ограниченията ни позволяват да използваме какъвто и да е метод на "грубата сила".

Подзадача 3: a, b<=100
Тази подзадача няма специфично решение. Тя е просто поставена от нас за да възнагради участниците, които поради някаква причина пълното им решение е бавно или грешно.

Подзадача 4: a, b<=10^5
Тук се намира пълното решение на задачата. Ако някой знае алогиртъма на Евклид, би разбрал бързо как да я реши. Идеята на този древен алгоритъм се основава на следното нещо:
Ако имаме две положителни цели числа a и b, можем да повтаряме следното:

Ако a > b, замести a със a - b
Ако b > a, замести b със b - a
Повтаряме, докато a != b

Крайното ни число е НОД.

Нека дам и един пример:
Да намерим НОД(48, 18)

48 > 18 → 48 - 18 = 30 → (30, 18)
30 > 18 → 30 - 18 = 12 → (12, 18)
18 > 12 → 18 - 12 = 6 → (12, 6)
12 > 6 → 12 - 6 = 6 → (6, 6)

→ НОД = 6
Нека да докажем и защо е правилен:
Нека имаме две положителни цели числа a и b. Без загуба на общност приемаме, че a ≥ b.

Твърдение:

НОД(a, b) = НОД(a − b, b)

Доказателство:

Нека d е общ делител на a и b. Това означава:

d | a (d дели a)
d | b (d дели b)

Следователно:

d | (a − b)
(защото разликата на две числа, които се делят на d, също се дели на d)

→ d е общ делител и на a − b и b.

Обратно:
Ако d | (a − b) и d | b, тогава:

d | (a − b + b) = a

→ Значи d е общ делител на a и b.

Следствие:

Общите делители на (a, b) и (a − b, b) са едни и същи
→ НОД(a, b) = НОД(a − b, b).

Изводи: 
Затруднение в тази задача е, че трябва да се пише подобие на машинен код.
Друго затруднение в имплементацията е липсата на функция за безусловно прескачане към даден ред. 
Това може да се реши със сравнение на някое число с регистър, който не се използва и винаги приема стойност 0 → RES := 0, след което се използва инструкция JZ.

Автор и решения: Димитър Шапатов
Анализ: Кирил Зашев