НОД

Напомним, что наибольшим общим делителем (НОД) для целых чисел a и b называют такое наибольшее число d, что a делится на d и b делится на d. При этом записывают это так: (a,b)=1 или НОД(a,b)=d или GCD(a,b)=d. Числа a и b называют взаимно простыми, когда НОД(a,b)=1. Данное определение обобщается и на набор чисел. При этом заметим, что попарной простоты недостаточно для подтверждения взаимной простоты набора чисел.

Наиболее функциональным и практичным методом поиска НОД является алгортим Евклида, который заключается в следующем: используя свойство НОД(a,b)=НОД(a, a mod b) мы можем свести данную запись к виду НОД(d,0), где d - искомый наибольший делитель. Другими словами, пока у нас оба числа a и b больше нуля следует наибольшее из них заменять на остаток от деления наибольшего на наименьшее, достаточно быстро мы получим таким образом решение задачи.

Реализация алгоритма Евклида для поиска НОД на алгоритмическом языке может выглядеть следующим образом:

read(a,b);
while a*b > 0 do 
  if a >= b then a = a mod b else b = b mod a;  
write(a+b); 

Наиболее красивая запись (но вовсе не самая понятная) решения этой задачи выглядит на языке С++ так:

#include <stdio.h>
#include <iostream.h>

int a,b;

int main(){
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
  cin >> a >> b;
  while(b) b^=a^=b^=a%=b;
  cout << a;
  return 0;
}

[Все попытки] [Задача]