C++ Number theory: Fastest way to compute max(y = a_i * x+ b_i) <= k

Question

following Problem, when having to make a fast code: I have a list of 2 integers a_i and b_i and I have to compute the equation: y = (a_i * x + b_i), where I'm only interested in y, not in x. All a_i's are prime and different from each other. a_i = y / x, b_i = y % x.

There are multiple solutions for y, even if y has to be the same for all a_i, b_i pairs, as x can be any integer number. Therefore we have an upper limit k and y <= k. I want to have the highest y possible (if there is a solution). max(y).

In short: I want to know the highest integer y (if there exists one), with y <= k and the equation given. x >= 1.

I already have a "solution" that works in theory, but that is too slow:

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;
}

Explanation: minK is max(a_i + b_i), as I thought that y = a_i *1 + b_i is the smallest possible solution for one equation, and as y is the same for all equations, the maximum one is the best lower bound.

stepSize is not 1 (in order to make the program faster), but max(a_i), as I thought, that as max(a_i) has to fit in y and y = a_i * x + b_i, therefore as x are integer values, the stepSize is a_i, and max(a_i) the best one, because that decreases the number of loop runs.

I now try out all y's from k to minK with stepSize and test for all pairs a_i and b_i, if they fulfill the equation. If one of them fails, I have to go on until I either find a solution or none (-1).

Unfortunately that algorithm is too slow (as a_i and b_i can go up to 10^12) and I can't think of any more optimizations. I already searched the internet for number theory and arithmetic's, but couldn't find any similar thing.

Can you help me to make this code faster or hint me to some sites, where this problem is handled?

Answer 1

You can satisfy for one i at a time while preserving all the ones already satisfied: step is the LCM of all the a[i] already satisfied (initially 1). y is the minimum value satisfying all the ones you did already. The key concept is that any Y satisfying all i must satisfy all the ones you already did, so it must be Y=y+n*step. So for each i you can directly compute the smallest n (if any) for which y+n*step mod a[i] equals b[i] and set y=y+n*step and step=lcm(step,a[i]). If there is no such n or if the new y is greater than k, then abort. Once you get through all i, you have the smallest y, but you wanted the largest y less than k, which is a trivial final adjustment since they differ by a multiple of step.