pomogite naiti opisanie GCD algoritma (greatest common divisor ) vi4isliaet naibolwii obwi delitel dvyx ili bolee 4isel?!      

гугл расширенный алгоритм евклида

По книге Стивена С. Скиены и Мигеля А. Ревиллы «ОЛИМПИАДНЫЕ ЗАДАЧИ ПО ПРОГРАММИРОВАНИЮ. Руководство по подготовке к соревнованиям» (Steven S. Skiena, Miguel A. Revilla. «PROGRAMMING CHALLENGES. The Programming Contest Training Manual»).
Глава 7. Теория чисел
7.2. Делимость
7.2.1. Наибольший общий делитель
7.2.2. Наименьшее общее кратное

Наибольший общий делитель

Так как на 1 делится любое целое число, то наименьшим общим делителем любой пары целых чисел a, b является 1. Интереснее рассматривать наибольший общий делитель, или НОД (GCD, Greatest Common Divisor), самый большой делитель, общий для двух заданных целых чисел. Рассмотрим дробь x/y, скажем 24/36. Мы можем получить приведённую форму этой дроби, если разделим числитель и знаменатель на НОД(x, y), равный в этом случае 12. Мы говорим, что два числа взаимно простые, если их НОД равен 1.

Алгоритм Евклида для нахождения наибольшего общего делителя считается первым интересным алгоритмом, который донесла до нас история. Чтобы найти НОД «в лоб», мы можем перебрать все делители первого числа и явно проверить, являются ли они делителями второго, или, как вариант, найти разложение на простые множители обоих чисел и взять произведение всех их общих множителей. Но и тот, и другой подход требует значительных вычислительных затрат.

Алгоритм Евклида основывается на двух наблюдениях.
1. Если b|a, то НОД(a, b) = b
   Это очевидно. Если a делится на b, то a = b*k для какого-то целого k, но тогда НОД(b*k, b) = b.
2. Если a = b*t + r для целых t и r, то НОД(a, b) = НОД(a, r).
   Почему? По определению НОД(a, b) = НОД(b*t + r, b). Любой общий делитель a и b должен делить r без остатка, так что очевидно, что b*t делится на любой делитель b.

Алгоритм Евклида -- это рекурсивное, повторяющееся замещение большего из двух чисел на остаток от целочисленного деления большего числа на меньшее. Обычно при этом один из аргументов уменьшается примерно вдвое, так что после логарифмического числа операций мы приходим к базовому случаю. Рассмотрим следующий пример. Пусть a = 34398 и b = 2132.


Таким образом НОД(34398, 2132) = 26.

Тем не менее из алгоритма Евклида мы можем найти не только НОД(a, b). С его помощью мы можем также найти целые x и y такие, что 
, 
что окажется весьма полезно при решении линейных сравнимостей. Мы знаем, что НОД(a, b) = НОД(b, a'), где a' = a - b*floor(a/b). floor(x) -- ближайшее целое, не превосходящее x. Более того, преположим, что из рекурсии мы знаем целые x' и y' такие, что 
.
Подставив наше выражение для a' в это выражение, получим: 
, 
тогда, приведя подобные, мы найдём искомые x и y. Чтобы наш алгоритм был полным, нам нужен базисный случай, он выбирается просто: a*1 + 0*0 = НОД(a, 0).

Для предыдущего примера мы получаем: 34398*15 + 2132*(-242) = 26. Вот реализация этого алгоритма (Расширенного алгоритма Евклида) на языке программирования Си: 



Сохраним код, например, в файлике gcd.c
И затем, если Вы используете компилятор GCC, то строка для компиляции может быть такой: 


Бонус: 

Наименьшее общее кратное

Ещё одной важной функцией от двух целых чисел является наименьшее общее кратное (НОК), самое маленькое целое число, которое делится на оба заданных целых числа. Например, наименьшее общее кратное 24 и 36 -- это 72.

Наименьшее общее кратное появляется в тех задачах, где требуется посчитать периодичность совпадения двух различных периодических событий. Когда в следующий раз (после 2000-го) год президентских выборов (которые проводятся каждые 4 года) совпадает с годом переписи населения (которая проводится раз в 10 лет)? Эти события совпадают каждые 20 лет, так как НОК(4, 10) = 20.

Очевидно, что НОК(x, y) >= max(x, y). Аналогично, так как x*y кратно и x, и y, то НОК(x, y) <= x*y. Меньшее ощее кратное может существовать только в том случае, если существует нетривиальный множитель, общий для x и y.

Это наблюдение вместе с алгоритмом Евклида даёт нам эффективный алгоритм вычисления наименьшего общего кратного, а именно НОК(x, y) = x*y/НОД(x, y). Более хитрый алгоритм, в котором нет необходимости в умножении и, как следствие, исчезает возможность переполнения, можно найти в книге E.W. Dijkstra. «Дисциплина прграммирования». 1976.


Это сообщение отредактировал(а) V.A.KeRneL - 15.1.2007, 04:32

spasibo bolwoe vsem kto otozvalsia!
tak je est xoroweeopisanie po adresy : http://en.wikipedia.org/wiki/Binary_GCD_algorithm