производительность — теория чисел C ++: самый быстрый способ вычислить max (y = a_i * x + b_i) & lt; = k

Следующая проблема, когда приходится делать быстрый код:
У меня есть список из 2 целых чисел a_i и b_i, и я должен вычислить уравнение:
y = (a_i * x + b_i), где меня интересует только y, а не x.
Все a_i просты и отличаются друг от друга. a_i = y / x, b_i = y% x.

Существует несколько решений для y, даже если y должно быть одинаковым для всех пар a_i, b_i, поскольку x может быть любым целым числом. Поэтому у нас есть верхний предел к и у <= к. Я хочу иметь максимально возможный у (если есть решение). макс (у).

Короче говоря: я хочу знать наибольшее целое число y (если оно существует), с y <= k и приведенное уравнение. х> = 1.

У меня уже есть «решение», которое работает в теории, но это слишком медленно:

struct part {
unsigned int size, rest;
};

int solve(vector<part> &partions, int minK, int stepSize, int k) {
int sol = 0;

for (int i = k; i >= minK; i -= stepSize) {
bool works = true;
for (int j = 0; j < static_cast<int>(partions.size()); j++) {
if ((i - partions[j].rest) % partions[j].size != 0) {
works = false;
break;
}
}
if (works) return i;
}return -1;
}

Пояснение: minK — это max (a_i + b_i), так как я думал, что y = a_i * 1 + b_i — это наименьшее возможное решение для одного уравнения, и, поскольку y одинаково для всех уравнений, максимальное значение является наилучшей нижней границей.

stepSize не 1 (для того, чтобы сделать программу быстрее), а max (a_i), как я думал, так как max (a_i) должен соответствовать y и y = a_i * x + b_i, поэтому x являются целочисленными значениями stepSize — a_i, а max (a_i) — лучший, потому что это уменьшает количество циклов.

Теперь я проверяю все y от k до minK с помощью stepSize и проверяю все пары a_i и b_i, если они удовлетворяют уравнению. Если один из них потерпит неудачу, мне придется продолжать, пока я не найду решение или ничего (-1).

К сожалению, этот алгоритм слишком медленный (так как a_i и b_i могут доходить до 10 ^ 12), и я не могу больше думать об оптимизации. Я уже искал в Интернете теорию чисел и арифметику, но не смог найти ничего подобного.

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