Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

НОД

(Время: 1 сек. Память: 16 Мб Сложность: 15%)

Напомним, что наибольшим общим делителем (НОД) для целых чисел 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;
}

[Обсуждение] [Все попытки] [Задача]


Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru