Расширенный Евклид

В то время как "обычный" алгоритм Евклида просто находит наибольший общий делитель двух чисел и , расширенный алгоритм Евклида находит помимо НОД также коэффициенты и такие, что:

Т.е. он находит коэффициенты, с помощью которых НОД двух чисел выражается через сами эти числа.

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<int> 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<max(a.size(),b.size()) || carry; ++i) {

if (i == a.size())

a.push_back (0);

a[i] += carry + (i < b.size()? b[i]: 0);

carry = a[i] >= base;

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

}

Г) Вычитание

int carry = 0;

for (size_t i=0; i<b.size() || carry; ++i) {

a[i] -= carry + (i < b.size()? b[i]: 0);

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<a.size() || carry; ++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<a.size(); ++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 – остаток