[MM] Задача про неточный НОД

soldatiki

Для двух целых чисел a и b нунжо найти два целых числа da и db так, чтобы НОД(a+da, b+db) был равен заданному числу D и сумма |da| + |db| была минимальна. И обратная задача: при фиксированном d = |da| + |db| найти наибольшее значние НОД(a+da, b+db). Желательно получить алгоритмы с невысокой вычислительной сложностью, например, O(1) относительно параметров D и d при условии, что допускается некоторый препроцессинг, например, разложение a и b на простые множители.

a101

Числа целые или натуральные?

a101



Для двух целых чисел a и b нунжо найти два целых числа da и db так, чтобы НОД(a+da, b+db) был равен заданному числу D и сумма |da| + |db| была минимальна.
Если не путаю, то НОД(a+da, b+db) = |d+1| НОД(a, b). |da| + |db| = |d| (|a| + |b|).
То есть если D = K * НОД(a, b то d = K - 1. Если D не делится на НОД(a, b то не существует такого d.
Может где-то что-то напутано в прямой задаче? Обратная тоже выглядит странно. Может нужно найти разые множители для a и b? Типо d_a и d_b?
 

Vadim46

Мне кажется, автор имел в виду, что da и db это типа \Delta a и \Delta b ;)

a101

О, клево. Что-то мои навыки телепатии с возрастом только уменьшаются. Посмотрим что можно сделать в этом случае )

a101



Для двух целых чисел a и b нунжо найти два целых числа da и db так, чтобы НОД(a+da, b+db) был равен заданному числу D и сумма |da| + |db| была минимальна. И обратная задача: при фиксированном d = |da| + |db| найти наибольшее значние НОД(a+da, b+db). Желательно получить алгоритмы с невысокой вычислительной сложностью, например, O(1) относительно параметров D и d при условии, что допускается некоторый препроцессинг, например, разложение a и b на простые множители.
1. Чтобы НОД(a+da, b+db) было равно D, надо (как минимум чтобы a+da и b+db делилось на D. Будем искать лучшее решение отдельно для 4 случаев (da > 0 и db > 0, da > 0 и db <= 0 ... ). Пусть da и db > 0. Тогда da = (D - (a mod D + D*K_a, db = (D - (b mod D + D*K_b (это чтобы НОД делился на D). После сокращения на D оказывается, что надо найти числа K_a и K_b, что НОД(a* + K_a, b* + K_b) = 1 (a* = (a + (D - (a mod D / D, b* = (b + (D - (b mod D / D).
2. Мы свели задачу к задаче, где D = 1 (кроме этого da >=0 и db >= 0). (Если я неправильно понял условие и нужно, чтобы НОД просто делился на D, то ничего больше делать не надо, просто берем K_a и K_b = 0.) Решаем каждую из 4 получившихся задач и потом выбираем лучшее решение. Как решать эту быстрее чем перебор непонятно и я бы просто перебирал все K_a и K_b, пока не нашел бы ближайшую. Просто перебирая (0, 0); (0, 1); (1, 0); (0, 2); (1, 1); (2, 0); (0, 3)... И проверял бы эту на взаимную простоту. Если не строить специфический тест (с большими числами специально сгенерированными то нужная точка попадается (в среднем) довольно быстро. Чтобы было еще быстрее, лучше перебирать K_a и K_b для 4 подзадач одновременно выбрав правильный порядок (чтобы как только нашли, можно было останавливаться). Сам алгоритм проверки на простоту через алгоритм Евклида работает очень быстро (O(log (min(n, m. Так что среднее время работы будет, думаю, O(log(|a|+|b|. Да и, думаю, худшее тоже того порядка.
3. Для обратной задачи ничего лучше, чем просто перебор по всем 4d возможным точкам у меня придумать тоже не получилась. Если просто их перебирать, то будет время O(d log(|a|+|b|. Точнее, если d у нас очень большое, то есть способы как-то уменьшить перебор, но если d порядка 10, то я бы просто все перебирал :( Если нетрудно, то напиши порядок d.

a101



3. Для обратной задачи ничего лучше, чем просто перебор по всем 4d возможным точкам у меня придумать тоже не получилась. Если просто их перебирать, то будет время O(d log(|a|+|b|. Точнее, если d у нас очень большое, то есть способы как-то уменьшить перебор, но если d порядка 10, то я бы просто все перебирал Если нетрудно, то напиши порядок d.
Вообще можно вот так еще ускорить, если d большое. Да и просто, возможно, это даст идеи для других ускорений.

Снова разобьем задачу на 4 подзадачи (по знакам da и db). Для случая da > 0 и db > 0 имеем НОД(a + da, b + db) = НОД(a + da, a + da + b + db) = НОД(a + da, a + b + d).
НОД (a + da, a + b + d) является делителем a+b+d. Перебираем теперь все делители a+b+d (надеясь что их меньше d) по убыванию и ищем первый (то есть максимальный) такой делитель q, что на отрезке [a, a+d] есть число делящиеся на q. Первое такое число и даст нам ответ. Проверка того, что на отрезке есть число, делящееся на q есть (a+d mod q) < d

soldatiki

Если нетрудно, то напиши порядок d
Мотороллер, как говорится, не мой, но насколько помню, da и db зависят от масштабов задачи и составляют что-то около пары процентов от a и b. Т. е. реально имеем вместо a+da произведение типа a*ka, ну и для b то же самое.
Воообще, большое спасибо за обстоятельный анализ, покажу это аффтору условия. Это ему поможет, думаю.
Оставить комментарий
Имя или ник:
Комментарий: