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

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

Утверждение: пусть 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-битный тип.

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

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

Найти наибольшую общую подпоследовательность двух строк - известная задача, и хорошо известно, как её решать за O(n*m). Однако, на википедии сказано, что существуют и другие, более быстрые алгоритмы. Хотелось бы узнать, какие они бывают.

Например есть такой алгоритм: заменить каждую букву строки B на упорядоченный по убыванию список вхождений этой буквы в строку A, а потом найти в этом списке наибольшую возрастающую подпоследовательность. К сожалению, этот алгоритм работает на двух строках вида aa...a длины n за время O(n^2 log n).

5

(2 ответов, оставленных в Algo)

Пытаюсь сдать вот эту задачу на Java. К сожалению преодолеть ML на 28 тесте пока не удалось, хотя в вершине бора хранится всего лишь 3 ссылки на вершины(суффиксная, на сына и на брата), byte - символ по которому мы приходим в нашу вершину из родителя и short - самая большая длина строки, заканчивающейся в этой вершине. Итого - 3*4 + 1 + 2 = 15 байт, все образцы занимают 100 килобайт, то есть примерно 10^5 вершин бора, всего 1.5 мегабайта. Но видимо из-за всяких бяк типа garbage collector'а занимается еще дофига памяти smile Однако перед тем, как переписывать всё это дело на массивы хочется узнать, есть ли какие-нибудь асимптотические оптимизации для потребления памяти(типа сжатого бора. Но тогда непонятно, как хранить все суффиксные ссылки для промежуточных вершин на ребре). Ну или неасимптотические smile

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

6

(1 ответов, оставленных в Feedback)

Правильно ли я понимаю, что описанный на этом сайте алгоритм не будет работать, если в графе будет цикл отрицательного веса?

7

(10 ответов, оставленных в Feedback)

Может кто-нибудь подскажет хорошую книжку про строки, в которой есть что-нибудь про суффиксные массивы?

8

(10 ответов, оставленных в Feedback)

Хммм, очень интересно как он работает например для строки acbacb.

9

(10 ответов, оставленных в Feedback)

А нету какого-нибудь простого алгоритма именно для LCP в отсортированном массиве циклических сдвигов, а не суффиксов?

10

(4 ответов, оставленных в Problems)

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

11

(8 ответов, оставленных в Offtopic)

e-maxx пишет:

Windows Server 2008 - 32%

Это, видимо, Windows 7 ?

12

(12 ответов, оставленных в Algo)

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

13

(4 ответов, оставленных в Problems)

Про treap есть отличная статья здесь http://e-maxx.ru/algo/treap big_smile

Ну а вообще суть решения в том, чтобы хранить все неудаленные числа в виде набора непересекающихся отрезков(тогда каждый запрос на удаление числа увеличит количество отрезков не более чем на 1).

14

(7 ответов, оставленных в Problems)

Насколько я понимаю, это и есть "физический смысл" функции Мебиуса. Думаю, что вот эта теорема и есть то, что используется в этой задаче.

15

(7 ответов, оставленных в Problems)

Sky code:

посчитаем массив s, s_i - это количество четверок чисел таких, что каждое из них делится на i. Ответом будет сумма по i от 1 до 10000 s_i*mu(i), где mu(i) - функция Мёбиуса

16

(2 ответов, оставленных в Feedback)

Видимо, я что-то недопонял, но зачем вообще тут нужно быстрое возведение в степень? Нам же надо только -1 возводить в степень, а это зависит просто от четности показателя.

И еще вопрос, можно как-нибудь за разумное время посчитать факториал n! по простому модулю p, если n порядка 10^18, а p порядка 10^9 ?

17

(9 ответов, оставленных в Algo)

Я уже решил ту задачу, там N было не больше 500 и даже три вложенных цикла прошли по времени.

18

(9 ответов, оставленных в Algo)

Глупый глупый я. Если вершинам приписать веса, равные разным степеням двойки, сконденсировать граф и заюзать этот алгоритм, то получится в точности флойд, а его быстрее, чем за куб не сделать hmm

19

(9 ответов, оставленных в Algo)

Решаю тут одну задачу и не могу придумать такой вот алгоритм:

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

Естественно, надо что-нибудь быстрее O(N^3) (N - количество вершин).

20

(1 ответов, оставленных в Problems)

Я эту задачу не решил, но по-моему это можно сделать так:

Отсортируем всех пиратов по азимуту. Теперь в любой момент времени потоплены будут все пираты на какой-то дуге окружности, проходящей через начальную точку(потому что если можно потопить пирата, то это надо сделать и хуже от этого не станет).

Таким образом у нас будет состояние динамики - (левая граница отрезка, правая граница отрезка, с какой стороны этого отрезка мы находимся). Хранится будет минимальное время, за которое всех можно на этом отрезке потопить, при этом не подпустив никого близко, или бесконечность. Для ответа надо перебрать все отрезки, покрывающие все корабли.

21

(5 ответов, оставленных в Problems)

Я решил эту задачу именно как автор темы, прошло за 0.39. В формуле, котрую я использовал, было N членов и в каждом биномиальные коэффициенты, но при этом соседние члены несильно отличались, и я просто хранил текущий член, пересчитывал и прибавлял к ответу.

22

(3 ответов, оставленных в Problems)

Кажется, что можно просто делить сначала на 9 пока делится, потом на 8, 7, ..., 2. Если в конце осталось не 1, то ответа нет. Иначе выводим то, на что делили, в обратном порядке. И плюс N=0 и N=1 разобрать отдельно.

23

(9 ответов, оставленных в Algo)

Когда мне нужно посмотреть что-нибудь по STL обычно хожу на cplusplus.com .

24

(9 ответов, оставленных в Algo)

Pair очень просто работает, если есть переменная var типа pair<T1,T2> где T1 и T2 любые типы, то можно обращаться к var.first - типа T1 или к var.second - типа T2. Ну и еще pair'ы сравниваются только по первым элементам из пары(т. е. var.first).

25

(30 ответов, оставленных в Problems)

ОК, убираем требование на :
1) целочисленность
2) положительность

весов ребер. Опять интересно посмотреть на контрпример.