Дано N пар целых чисел Ai,Bi, причем Ai>Bi и нет равных Ai,Aj.
Найти минимальное M, которое при делении на Ai даст в остатке Bi.

Или в олимпиадной трактовке:

Входной файл: в первой строке целое N>1, далее в N строках пары целых Ai,Bi, причем Ai>Bi и нет равных Ai,Aj.
Выходной файл: минимальное положительное M, которое при делении на любое из данных Ai даст в остатке Bi.

Пример:

Входной файл
3
3 1
4 2
7 2

Выходной файл
58

Примечания: 
1) Хоть среди чисел Ai нет равных, это не значит, что все они взаимно просты...
2) Некоторые Bi могут быть равны нулю

Само собой, достаточно описать алгоритм поиска такого M. Плюс алгоритм обнаружения, что входные данные противоречивы.

в общем, у меня вот так получилось:



наверное, можно как-то умнее, но тогда, видимо, придётся заниматься факторизацией, что тоже трудоёмко и неизвестно отобьёт ли свои затраты.

Перебор - не решение. Пусть и с самым большим возможным шагом. А есмли пойдет речь о  работе в сверхдлинных числах? Программа не отработает до конца, потому что комп в пыль рассыплется от старости.

Добавлено через 8 минут и 14 секунд
Сосбственно суть задачи - именно в поиске зависимостей, способных уйти от перебора или значимо его оптимизировать.

для Bi-ых равных нулю, искомое есть произведение простых чисел в наибольшей степени полученных после факторизации всех Ai. по-идее, это можно адаптировать и под ненулевые Bi. перебора нет, но для сверхбольших чисел факторизация - та ещё задачка и от перебора не особо отличается. ничего другого в голову не приходит.

.. оО! кое-что пришло в голову! ща буду проверять, не говори решение.  

Решение? а его пока нет... есть уже найденные способы вполне серьезной оптимизации - но тем не менее рассчет начинает безбожно тормозить уже на полусотне входных пар.

Есть вот такая наивная идея: группируем все Ai для каждого из различных Bj. (M - Bj) должно делиться на НОК Ai соответствующей группы (в примере, M-2 должно делиться на 28). Находим среди всех НОК групп наибольшее и пробуем числа-кандидаты с таким шагом, проверяя, выполнятся ли для него остальные условия (делится ли оно на НОК других групп с требуемым остатком). Номера шагов, кратные хотя бы одному из чисел Ai, вошедших в другие группы, очевидно, пропускаем. Также очевидно, что если в какой-то группе хотя бы одно число Ai кратно другому, то достаточно пропускать шаги, кратные минимальному из них. 

Если какое-то из чисел Ai кратно числу Aj из другой группы - входные данные противоречивы (пример - пары входных чисел 4, 2 и 8, 5).

Для приведенного примера: явного признака противоречивости данных нет, есть две группы по остатку. В группе с остатком 1 - 1 число, НОК=3; группа с остатком 2 - 2 числа, НОК = 28. Следовательно, шаг перебора = 28.
Первый кандидат = 28*1+2 = 30. Проверяем, остаток от деления на 3 равен 0, а не 1 - не подходит.
Второй кандидат = 28*2+2 = 58. Проверяем, остаток от деления на 3 равен 1. Ответ найден.

Если бы второй кандидат не подошел, то проверять третьего кандидата не имело бы смысла, т.к. 28*3+2 автоматически не может делиться на 3 с единицей в остатке. Проверять числа, бОльшие, чем НОК всех Ai, имхо тоже нет смысла, потому что ситуация с остатками полностью повторяется с такой периодичностью. Так что достижение этого порога - второй критерий противоречивости входных данных.

Можно ли считать это существенной оптимизацией перебора?

Это сообщение отредактировал(а) SelenIT - 17.12.2007, 08:31

выдай их, плиз, чтобы на одних данных тестировали.

Это пока одна из двух оптимизаций, давшая существенный эффект. Вторая - разделение Ai на простые делители Aij для каждого Ai,Bi и просчет соотв. Bij. Заодно именно в этот момент происходит проверка валидности входных данных. Построение сетки остатков на пространстве НОД хотя и обещало изрядное ускорение, но на практике для НЕ взаимно простых Ai,Aj оказалось излишне вычислительноемким.


Реальные данные имеют приблизительно следующие ограничения:
10<N<1000
100<A<1000000
0<B<A/2

Так что вполне можно тестировать скорость на, скажем



Однако результат гарантированно вылетает за int64...

фуф, ну кажися сделал:


вкратце, идея такова, происходит решение линейных диафантовых уравнений с двумя неизвестными, т.е. решение аналитическое. каждое решение позволяет создать пересечение решений уже решённых уравнений и очередной пары, и в итоге это приводит (или не приводит при отсутствии решений\пересечений) к одной паре At + B, M = B при t = 0, или при B равном 0, М = А, что требуется по условию задачи. трудоёмкость алгоритма, как можно заметить, пропорциональна N, но оптимизировать ещё много куда есть. 

спасибо, хорошая задачка. основательно подучил теорию чисел, за два дня с нуля.  

Теперь осталось мне, с моим практически нулевым знанием Си, во всем этом разобраться... но это уже чисто технический вопрос.

это C#, он попроще немного. 

.. поподробнее. нужно решить систему уравнений в целых числах:

A1 * X1 + B1 = M
A2 * X2 + B2 = M
..
Ai * Xi + Bi = M

неизвестные: Xi и М. система недопределена, поэтому решений, если таковые имеются, множество. как это водится для таких систем будем решать следующим образом, избавимся от M:

A1 * X1 + B1 = A2 * X2 + B2

замечаем, что это обычное линейное диафантово уравнение с двумя неизвестными:

A1 * X1 - A2 * X2 = B2 - B1

его решения выражаются, в данном случае, как:

X1 = Z1 + A2 * t
X2 = Z2 + A1 * t

Z1 = (B2 - B1) * U и Z2 = (B2 - B1) * V, U и V - коэффициенты Безу. самое замечательное, что после решения этого уравнения X1 и X2 выражаются через одну переменную t, подставив в исходное уравнение получаем:

A1 * (Z1 + A2 * t) + B1 = A2 * (Z2 + A1 * t) + B2
A1 * A2 * t + A1 * Z1 + B1 = A1 * A2 * t + A2 * Z2 + B2 - что является верным тождеством.

выходит, что уравнение с двумя неизвестными мы свели к одному с одним неизвестным t и теперь вправе воспользоваться одной из частей тождества. дальше всё просто:

A1 * A2 * t + A1 * Z1 + B1 = A3 * X3 + B3

решаем тем же способом, выражаем через одну переменную, и так далее в том же духе для всех Ai * Xi + Bi. при подстановке реальных чисел главное не забывать сокращать коэффициент при t на наибольший общий делитель, полученный при вычислении U и V, и приводить данные к нормализованному виду - при необходимости, A1 * Z1 + B1 делить по модулю на A1 * A2 и выражать в положительных числах по тому же модулю.

в итоге, получается одно уравнение-решение всей системы, которое является пересечением всех индивидуальных решений исходных уравнений в исходной системе:

AF * t + BF = M

т.к. мы решаем в целых числах и BF < AF и AF > 0 (из природы данных), то M = AF * 0 + BF = BF или M = AF * 1 при BF = 0.