1

Тема: Расширенный алгоритм Евклида - зависимость ответа от начальных данных

Есть ли какие-нибудь оценки на промежуточные и получаемые значения, если известны оценки на A и B? Мне почему-то кажется, что получится либо A*B либо max(A, B). В кормене и английской википедии об этом ни слова(ну или я плохо смотрел)

2 Отредактировано 2rf (2012-11-21 17:57:12)

Re: Расширенный алгоритм Евклида - зависимость ответа от начальных данных

Ага, что-то я погорячился, надо было чуть-чуть подумать, зато теперь я всё строго доказал! Для потомков изложу доказательство тут:

Утверждение: пусть x, y - результат работы расширенного алгоритма Евклида для неотрицательных чисел a, b. Тогда |x| ≤ b, |y| ≤ a.
Доказательство: по индукции. База - (a = 0 к сожалению не подходит) b делится на a, x = 1, y = 0, b ≠ 0, поэтому всё в порядке.

Переход - пусть из пары (b, bq + a) (a < b, q ≥ 0) мы попали в пару (a, b), для которой результат - (x, y). Тогда для первой пары результат будет (y-qx, x). Оценим: |y-qx| ≤ |y| + |qx| ≤ a + qb, |x| ≤ b(в неравенствах мы применяем предположения индукции), получили требуемое.

Но вообще изначально я создал тему вот из-за чего: надо было решить уравнение Ax+By=C, где A, B и C от 0 до 10^18. Пусть для простоты gcd(A, B) = 1, тогда для этого мы находим корень (x0, y0) уравнения Ax+By=1, и все решения нашего уравнения выглядят так: (C * x0 + B * n, C * y0 - A * n), n ∈ Z. Проблема - С * x0 теперь до 10^36, а тем не менее мне почему-то кажется, что всегда должен быть корень, влезающий в 64-битный тип.

Короче говоря вопрос, можно ли решить такую задачу без использования длинной арифметики?

3

Re: Расширенный алгоритм Евклида - зависимость ответа от начальных данных

Всё опять довольно просто: можно взять x = (C * x0) % B, y = (C - A * x) / B. Единственная проблема - надо вычислять a * b % c и a * b / c, но это можно сделать при помощи бинарного умножения. Наверняка есть решение еще попроще, буду рад узнать.