На головну

Розширений Евклід

  1. Поверхня в Евклідовому просторі

У той час як "звичайний" алгоритм Евкліда просто знаходить найбільший спільний дільник двох чисел и  , Розширений алгоритм Евкліда знаходить крім НСД також коефіцієнти и  такі, що:

Тобто він знаходить коефіцієнти, за допомогою яких НСД двох чисел виражається через самі ці числа.

int gcd (int a, int b, int & x, int & y) {

if (a == 0) {

x = 0; y = 1;

return b;

}

int x1, y1;

int d = gcd (b% a, a, x1, y1);

x = y1 - (b / a) * x1;

y = x1;

return d;

}

Длінка

структура даних

Зберігати довгі числа будемо у вигляді вектора чисел  , Де кожен елемент - це одна цифра числа.

typedef vector lnum;

Для підвищення ефективності будемо працювати в системі по підставі мільярд, тобто кожен елемент вектора  містить не одну, а відразу  цифр:

const int base = 1000 * 1000 * 1000;

Цифри будуть зберігатися у векторі в такому порядку, що спочатку йдуть найменш значущі цифри (тобто одиниці, десятки, сотні, і т.д.).

Крім того, всі операції будуть реалізовані таким чином, що після виконання будь-якої з них лідируючі нулі (тобто зайві нулі на початку числа) відсутні (зрозуміло, в припущенні, що перед кожною операцією лідируючі нулі також відсутні). Слід зазначити, що в представленій реалізації для числа нуль коректно підтримуються відразу дві вистави: порожній вектор цифр, і вектор цифр, що містить єдиний елемент - нуль.

А) Висновок

printf ( "% d", a.empty ()? 0: a.back ());

for (int i = (int) a.size () - 2; i> = 0; --i)

printf ( "% 09d", a [i]);

Б) Читання

for (int i = (int) s.length (); i> 0; i- = 9)

if (i <9)

a.push_back (atoi (s.substr (0, i) .c_str ()));

else

a.push_back (atoi (s.substr (i-9, 9) .c_str ()));

В) Додавання

int carry = 0;

for (size_t i = 0; i

if (i == a.size ())

a.push_back (0);

a [i] + = carry + (i

carry = a [i]> = base;

if (carry) a [i] - = base;

}

Г) Віднімання

int carry = 0;

for (size_t i = 0; i

a [i] - = carry + (i

carry = a [i] <0;

if (carry) a [i] + = base;

}

while (a.size ()> 1 && a.back () == 0)

a.pop_back ();

Д) Множення довгого на короткий

int carry = 0;

for (size_t i = 0; i

if (i == a.size ())

a.push_back (0);

long long cur = carry + a [i] * 1ll * b;

a [i] = int (cur% base);

carry = int (cur / base);

}

while (a.size ()> 1 && a.back () == 0)

a.pop_back ();

Е) Множення двох довгих чисел

lnum c (a.size () + b.size ());

for (size_t i = 0; i

for (int j = 0, carry = 0; j <(int) b.size () || carry; ++ j) {

long long cur = c [i + j] + a [i] * 1ll * (j <(int) b.size ()? b [j]: 0) + carry;

c [i + j] = int (cur% base);

carry = int (cur / base);

}

while (c.size ()> 1 && c.back () == 0)

c.pop_back ();

Ж) Ділення довгого на короткий

int carry = 0;

for (int i = (int) a.size () - 1; i> = 0; --i) {

long long cur = a [i] + carry * 1ll * base;

a [i] = int (cur / b);

carry = int (cur% b);

}

while (a.size ()> 1 && a.back () == 0)

a.pop_back ();

carry - залишок

 



Алгоритм Куна знаходження найбільшого паросполучення в дводольному графі | дискретного логарифмування

Флойд-Уоршелл | Алгоритм пошуку компонент зв'язності в графі | Пошук точок зчленування | Теорема Піка. | Z-функція рядка і її обчислення | Знаходження наідліннейшей зростаючої підпослідовності | Знаходження найбільшою нульовий подматріци | Біноміальні коефіцієнти | числа Каталана | намиста |

© um.co.ua - учбові матеріали та реферати