Алгоритмы C++

с умножением.

Виды дробной длинной арифметики

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

Длинная арифметика в несократимых дробях

Число представляется в виде несократимой дроби , где и — целые числа. Тогда все операции над дробными числами нетрудно свести к операциям над числителями и знаменателями этих дробей.

Обычно при этом для хранения числителя и знаменателя приходится также использовать длинную арифметику, но, впрочем, самый простой её вид — Классическая длинная арифметика, хотя иногда достаточно применения для них 64-битного встроенного типа.

Выделение позиции плавающей точки в отдельный тип

Иногда в задаче требуется производить расчёты с очень большими либо очень маленькими числами, но при этом не допускать их переполнения. Встроенный 8-байтовый тип double, как известно, допускает значения экспоненты в диапазоне , чего иногда может оказаться недостаточно.

Приём, собственно, очень простой — вводится ещё одна целочисленная переменная, отвечающая за экспоненту, а

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

Наконец, понятно, что не обязательно выбирать 10 в качестве основания экспоненты. Исходя из устройства встроенных типов с плавающей точкой, самым выгодным представляется класть основание равным 2.

Функция производит собственно решение задачи.

int powmod (int a, int b, int m) { int res = 1;

while (b > 0) if (b & 1)

res = (res * a) % m, --b;

else

a = (a * a) % m, b >>= 1; return res;

}

int solve (int a, int b, int m) {

int msq = (int) sqrt (m + .0) + 1;

int msq2 = m / msq + (m % msq ? 1 : 0); vector < pair<int,int> > vals (msq2); for (int i=1; i<=msq2; ++i)

vals[i-1] = make_pair (powmod (a, i * msq, m), i); sort (vals.begin(), vals.end());

for (int i=0; i<=msq; ++i) {

int cur = powmod (a, i, m); cur = (cur * b) % m;

vector < pair<int,int> > ::iterator it =

lower_bound (vals.begin(), vals.end(), make_pair (cur, 0)); if (it != vals.end() && it->first == cur)

return it->second * msq - i;

}

return -1;

}

Получение всех решений

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

Итак, пусть , а числа удовлетворяют условию:

Тогда заметим, что, прибавив к число и одновременно отняв от , мы не нарушим равенства:

Очевидно, что этот процесс можно повторять сколько угодно, т.е. все числа вида:

являются решениями диофантова уравнения.

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

Нахождение количества решений и сами решения в заданном отрезке

любое решение диофантова уравнения (см. пункт 1). Затем получим из него решение с наименьшим

— воспользуемся процедурой, описанной в предыдущем пункте, и будем уменьшать/увеличивать , пока оно не попадёт в заданный отрезок, и при этом будет наименьшим. Это можно сделать за таким образом:

int

a, b, c, g, // коэффициенты диофантова уравнения, и g=gcd(a,b) x0, y0, // одно из решений диофантова уравнения

x1, x2, // заданный отрезок

mx, my; // искомое решение с наименьшим x >= x1 int cnt = (x1 - x0) / b;

if (x0 + cnt * b < x1) ++cnt;

mx = x0 + cnt * b; my = y0 - cnt * b;

Здесь предполагается, что (если , то нужно предварительно изменить знаки ). Аналогичным образом найдём решение с наибольшим .

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

Нахождение решения в заданном отрезке с наименьшей суммой x+y

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

Идея решения такая же, как и в предыдущем пункте: сначала находим любое решение диофантова уравнения, а

затем, применяя описанную в предыдущем пункте процедуру, придём к наилучшему решению. Действительно, мы имеем право выполнить следующее преобразование (см. предыдущий пункт):

Заметим, что при этом сумма меняется следующим образом:

Модульное линейное уравнение первого порядка

Постановка задачи

Это уравнение вида:

где — заданные целые числа, — неизвестное целое число.

Решение с помощью нахождения Обратного элемента

Рассмотрим сначала более простой случай — когда и взаимно просты. Тогда можно найти обратный элемент к числу , и, домножив на него обе части уравнения, получить решение (и оно будет единственным):

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

Пусть , т.е. их наибольший общий делитель (который в данном случае больше единицы).