<commit_before>---
layout: post
title:  "Алгоритм Евклида нахождения НОД, НОК"
date:   2016-11-01
categories: [tutorial, arithmetic]
tags: [easy, gcd, lcm, arithmetic]
author: <NAME>
---

Пусть даны два целых числа $$x$$ и $$y$$.
Не нарушая общности, положим, что $$x > 0$$ и $$y > 0$$, в противном случае заменяем отрицательное число на обратное.

Число $$k$$ называют общим делителем, если $$k \mid x$$ (говорят $$k$$ делит $$x$$) и $$k \mid y$$.
Тогда $$\exists ! g$$ - общий делитель такой, что $$\forall k$$ $$k \mid g$$, такой общий делитель $$g$$ называют наибольшим общим делителем, и обозначают $$g = НОД(x, y)$$.
<!-- more -->

## Алгоритм Евклида для целых чисел

Можно предположить, что $$x > y$$, в противном случае просто поменяем $$x$$ и $$y$$.
Тогда $$x$$ можно поделить с остатком на $$y$$:

$$
x = y\cdot q_0 + r_1,
$$

$$q_0$$ называют неполным частным, а $$r_1$$ - остатком от деления, причём $$0 \leq r_1 < y$$.
Далее поделим с остатком $$y$$ на $$r_1$$:

$$
y = r_1\cdot q_1 + r_2,
$$

продолжая так далее на некотором шаге $$n$$ остаток $$r_n$$ окажется равным нулю, таким образом получаем последовательность:

$$
x > y > r_1 > r_2 > \dots > r_{n-1} > 0.
$$

Тогда $$НОД(x, y)$$ - наибольший общий делитель $$x$$ и $$y$$ будет равен $$r_{n-1}$$.

Формально алгоритм будет иметь вид:

$$
\begin{equation*}
НОД(x, y) = 
 \begin{cases}
   x, &y = 0\\
   НОД(y, x\pmod{y}), &y > 0
 \end{cases}
\end{equation*}
$$

### Корректность

Пусть $$x = y\cdot q + r$$, тогда $$НОД(x, y) = НОД(y, r)$$.

$$НОД(r, 0) = r$$, $$\forall r > 0$$

### Реализация

#### Рекурсивная
{% highlight cpp %}
int GCD(const int x, const int y) {
    if (y == 0)
        return x;
    return GCD(y, x%y);
}
{% endhighlight %}

#### Нерекурсивная
{% highlight cpp %}
int GCD(const int x, const int y) {
    int r1(x), r2(y);
    while (r2 > 0) {
        r1 %= r2;
        swap(r1, r2);
    }
    return r1;
}
{% endhighlight %}

## НОК

Число $$m$$ называют общим кратным, если $$x\mid m$$ и $$y\mid m$$.

Тогда $$\exists ! n$$ - общее кратное такое, что $$\forall m$$ $$n \mid m$$, такое общее кратное $$n$$ называют наименьшим общим кратным, и обозначают $$n = НОК(x, y)$$.

Вычисление наименьшего общего кратного сводится к вычислению наибольшего общего делителя:

$$
НОК(x, y) = \frac{x\cdot y}{НОД(x, y)}
$$

### Реализация

{% highlight cpp %}
int LCM(const int x, const int y) {
    return x/GCD(x, y)*y;
}
{% endhighlight %}

### Практика

+ НОД:
    - [mccme 111234](http://informatics.mccme.ru/moodle/mod/statements/view3.php?chapterid=111234) 
    - [mccme 147](http://informatics.mccme.ru/mod/statements/view3.php?chapterid=147) 
+ НОК: 
    - [mccme 146](http://informatics.mccme.ru/mod/statements/view3.php?chapterid=146)
    - [mccme 1422](http://informatics.mccme.ru/mod/statements/view3.php?chapterid=1422)<commit_msg>task's open in new tab<commit_after>---
layout: post
title:  "Алгоритм Евклида нахождения НОД, НОК"
date:   2016-11-01
categories: [tutorial, arithmetic]
tags: [easy, gcd, lcm, arithmetic]
author: <NAME>
---

Пусть даны два целых числа $$x$$ и $$y$$.
Не нарушая общности, положим, что $$x > 0$$ и $$y > 0$$, в противном случае заменяем отрицательное число на обратное.

Число $$k$$ называют общим делителем, если $$k \mid x$$ (говорят $$k$$ делит $$x$$) и $$k \mid y$$.
Тогда $$\exists ! g$$ - общий делитель такой, что $$\forall k$$ $$k \mid g$$, такой общий делитель $$g$$ называют наибольшим общим делителем, и обозначают $$g = НОД(x, y)$$.
<!-- more -->

## Алгоритм Евклида для целых чисел

Можно предположить, что $$x > y$$, в противном случае просто поменяем $$x$$ и $$y$$.
Тогда $$x$$ можно поделить с остатком на $$y$$:

$$
x = y\cdot q_0 + r_1,
$$

$$q_0$$ называют неполным частным, а $$r_1$$ - остатком от деления, причём $$0 \leq r_1 < y$$.
Далее поделим с остатком $$y$$ на $$r_1$$:

$$
y = r_1\cdot q_1 + r_2,
$$

продолжая так далее на некотором шаге $$n$$ остаток $$r_n$$ окажется равным нулю, таким образом получаем последовательность:

$$
x > y > r_1 > r_2 > \dots > r_{n-1} > 0.
$$

Тогда $$НОД(x, y)$$ - наибольший общий делитель $$x$$ и $$y$$ будет равен $$r_{n-1}$$.

Формально алгоритм будет иметь вид:

$$
\begin{equation*}
НОД(x, y) = 
 \begin{cases}
   x, &y = 0\\
   НОД(y, x\pmod{y}), &y > 0
 \end{cases}
\end{equation*}
$$

### Корректность

Пусть $$x = y\cdot q + r$$, тогда $$НОД(x, y) = НОД(y, r)$$.

$$НОД(r, 0) = r$$, $$\forall r > 0$$

### Реализация

#### Рекурсивная
{% highlight cpp %}
int GCD(const int x, const int y) {
    if (y == 0)
        return x;
    return GCD(y, x%y);
}
{% endhighlight %}

#### Нерекурсивная
{% highlight cpp %}
int GCD(const int x, const int y) {
    int r1(x), r2(y);
    while (r2 > 0) {
        r1 %= r2;
        swap(r1, r2);
    }
    return r1;
}
{% endhighlight %}

## НОК

Число $$m$$ называют общим кратным, если $$x\mid m$$ и $$y\mid m$$.

Тогда $$\exists ! n$$ - общее кратное такое, что $$\forall m$$ $$n \mid m$$, такое общее кратное $$n$$ называют наименьшим общим кратным, и обозначают $$n = НОК(x, y)$$.

Вычисление наименьшего общего кратного сводится к вычислению наибольшего общего делителя:

$$
НОК(x, y) = \frac{x\cdot y}{НОД(x, y)}
$$

### Реализация

{% highlight cpp %}
int LCM(const int x, const int y) {
    return x/GCD(x, y)*y;
}
{% endhighlight %}

### Практика

+ НОД:
    - [mccme 111234](http://informatics.mccme.ru/moodle/mod/statements/view3.php?chapterid=111234){:target="_blank"} 
    - [mccme 147](http://informatics.mccme.ru/mod/statements/view3.php?chapterid=147){:target="_blank"}
+ НОК: 
    - [mccme 146](http://informatics.mccme.ru/mod/statements/view3.php?chapterid=146){:target="_blank"}
    - [mccme 1422](http://informatics.mccme.ru/mod/statements/view3.php?chapterid=1422){:target="_blank"}
{'fraction_non_alphanumeric': 0.19340774328566446, 'fraction_numerical': 0.026159748866410884, 'mean_word_length': 3.632471728594507, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 31, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3684224', 'n_tokens_mistral': 2744, 'n_tokens_neox': 2747, 'n_words': 673}