# SEQUAT2 - Editorial

Author: Istvan Nagy
Tester: Kevin Atienza
Translators: Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza

Medium-Hard

### PREREQUISITES:

Bitwise operations, sieve, factorization

### PROBLEM:

Given A, B, C, N, compute all solutions (x,y) to the following equation:

xy = (x\lor y)(x\land y) + Ax + By + C

where \lor and \land are bitwise OR and AND, respectively.

Compute the sum of all x and sum of all y across all solutions (x,y) with 0 \le x, y \le N.

### QUICK EXPLANATION:

Let n = x\land y, a = x-n and b = y-n. Then thereâ€™s a one-to-one mapping between solutions (x,y) and triples (a,b,n) such that:

• a\land b = a\land n = b\land n = 0.
• (a-B)(b-A) = (A+B)n+AB+C.

The mapping is given by (x,y) = (a+n,b+n).

Let L = (A+B)N+AB+C. Notice that (a-B)(b-A) \le L, and the smaller of (a-B) and (b-A) is \le \sqrt{L}.

To compute all solutions (a,b,n) such that (a-B) \le (b-A):

• Enumerate all possible values of d := a-B up to \sqrt{L}.
• Compute all numbers n such that (A+B)n+AB+C is divisible by d.
• Let e = \frac{(A+B)n+AB+C}{d}. If e \le d, then try the solution (d+B, e+A, n).

Similarly, to compute all solutions (a,b,n) such that (a-B) > (b-A):

• Enumerate all possible values of e := b-A up to \sqrt{L}.
• Compute all numbers n such that (A+B)n+AB+C is divisible by e.
• Let d = \frac{(A+B)n+AB+C}{e}. If e < d, then try the solution (d+B, e+A, n).

Using this, every solution will be generated exactly once, but you need to check each candidate (a,b,n) if it satisfies all conditions above.

# Reparameterization

The equation xy = (x\lor y)(x\land y) + Ax + By + C is very weird because of the bitwise operations. You donâ€™t normally see those, which makes this problem unusual. Nevertheless, bitwise operations still behave somewhat well algebraically, so letâ€™s see what we can do.

The first thing we note is that if two numbers a and b donâ€™t share any bits, then (a\lor b) = a+b and (a\land b) = 0. But what if they donâ€™t share any bits? Then the first one is incorrect, because it fails to take into account the bits shared by a and b. Specifically, these bits are counted twice in a+b but only once in (a\lor b).

But we can easily know which bits two numbers share: itâ€™s simply (a\land b)! Thus, this gives us the following general identity:

(a\lor b) = a+b - (a\land b)

This is great, because it eliminates one nasty bitwise operator! Now we have one more left. Our equation is now:

xy = (x+y - (x\land y))(x\land y) + Ax + By + C

(Youâ€™ll notice that there are too many parentheses in these equations. This is because bitwise operations are that uncommon among math equations.)

If we let n = x\land y, then the equation becomes:

xy = (x+y - n)n + Ax + By + C

Now weâ€™re getting somewhere. Notice that the bitwise operations are disappearing.

In fact, letâ€™s take this idea further, and reparameterize the solutions so that our variables donâ€™t have bits in common. Currently, we have the values (x,y,n), but these numbers may have bits in common. So letâ€™s define new variables a = x-n and b = y-n to denote the bits unique to x and y, respectively. This way, for a triple (a,b,n), we have (a\land b) = (a\land n) = (b\land n) = 0 and

(a+n)(b+n) = ((a+n)+(b+n) - n)n + A(a+n) + By + C

Letâ€™s manipulate this further:

\begin{aligned} (a+n)(b+n) &= ((a+n)+(b+n) - n)n + A(a+n) + B(b+n) + C \\ (a+n)(b+n) &= (a+b+n)n + A(a+n) + B(b+n) + C \\ ab+an+bn+n^2 &= an+bn+n^2 + A(a+n) + B(b+n) + C \\ ab &= A(a+n) + B(b+n) + C \end{aligned}

Notice the nice cancellation going on! This is certainly easier to solve.

At this point though, it isnâ€™t clear how to proceed. But if you assume for a while that n is a constant, then we notice that the equation becomes a conic section on the variables a and b, and it turns out that such equations are usually reducible to one of the following:

• A linear diophantine equation
• Generalized Pell equation
• Factorization problem

Letâ€™s see what we got by assuming n is constant and throwing all â€śconstantsâ€ť to the right side:

\begin{aligned} ab &= A(a+n) + B(b+n) + C\\ ab - Aa - Bb &= (A+B)n + C \end{aligned}

Here, we can try to â€ścomplete the factorizationâ€ť:

\begin{aligned} ab - Aa - Bb &= (A+B)n + C\\ ab - Aa - Bb+AB &= (A+B)n + AB + C \\ (a-B)(b-A) &= (A+B)n + AB + C \end{aligned}

This means we have reduced the problem to factorizing all numbers of the form (A+B)n + AB + C, where n \le N

# Enumerating factors

Now weâ€™re really getting somewhere. We want to enumerate the triples (a,b,n) satisfying all the following things:

• (a-B)(b-A) = (A+B)n + AB + C.
• a+n \le N and b+n \le N.
• (a\land b) = (a\land n) = (b\land n) = 0.

The remaining two conditions can just be checked afterwards, so letâ€™s focus on the first, i.e. enumerating factorizations of (A+B)n + AB + C.

This number is always positive, but the factors on the left side may be negative! Thankfully, we can exclude that possibility because if both factors are negative (and a, b \ge 0), then |(a-B)(b-A)| \le |AB| < (A+B)n + AB + C. Thus, we can focus on positive divisors.

Next, notice that the largest possible right-hand-side value is L := (A+B)N + AB + C. This means that the smaller factor among (a-B) and (b-A) is at most the square root of this number. But the square root of this number is a smallish number considering the problem constraints, which makes it feasible for enumeration!

Specifically, assume first that (a-B) \le (b-A). This means that (a-B) \le \sqrt{L}. So letâ€™s enumerate all these possible values d := a-B. The next step is to enumerate all indices n \le N such that d divides (A+B)n + AB + C. Which such indices are there?

If we let P = A+B and Q = AB + C, then the following are equivalent:

\begin{aligned} d &\mid (A+B)n + AB + C \\ d &\mid Pn + Q \\ Pn &\equiv -Q \pmod{d} \end{aligned}

Let g = \gcd(P,d). Then if g doesnâ€™t divide Q, this has no solutions. Otherwise, we can continue by letting P' = P/g, Q' = Q/g and d' = d/g:

\begin{aligned} Pn &\equiv -Q \pmod{d} \\ P'n &\equiv -Q' \pmod{d'} \\ n &\equiv -Q'(P')^{-1} \pmod{d'} \end{aligned}

This means that itâ€™s easy to â€śloopâ€ť across all valid indices n! The following is an illustration on how this can be done, using a C+Â±style loop:

    Let g = gcd(P,d)
Let x = modInverse(P/g,d/g)
for (n = (-Q'*x) % (d/g); n <= N; n += d/g) {
...
}


Having access to d and n, we can now compute a candidate solution (a,b,n) as:

• a = B + d (from d = a-B)
• b = A + \frac{(A+B)n+AB+C}{d}
• n = n

(You should only count this if (a-B) \le (b-A) is true.)

Using this method, we can enumerate all candidate solutions (a,b,n) satisfying (a-B) \le (b-A).

We can enumerate candidates (a,b,n) satisfying the other inequality (b-A) < (a-B) similarly:

• b = A + d
• b = B + \frac{(A+B)n+AB+C}{d}
• n = n

(You should only count this if (b-A) < (a-B) is true.)

Since every solution (a,b,n) determines a unique value (a-B)(b-A), this means each solution will be generated exactly once! We just need to filter out the candidates with the remaining requirements:

• a+n \le N and b+n \le N.
• (a\land b) = (a\land n) = (b\land n) = 0.

# Running time

The question now is, how fast does this solution run?

Notice that for every number d \le \sqrt{L}, the number of candidates weâ€™re considering is at most:

1 + \frac{N}{d/\gcd(A+B,d)}

Thus, the running time is proportional to the following sum:

\sum_{d\le \sqrt{L}} \left(1 + \frac{N}{d/\gcd(A+B,d)}\right)

Which can be simplified to:

\begin{aligned} T(N) &= O\left(\sum_{d\le \sqrt{L}} \left(1 + \frac{N}{d/\gcd(A+B,d)}\right)\right) \\ &= O\left(\sqrt{L} + \sum_{g \mid A+B} \sum_{{d\le \sqrt{L}, \gcd(A+B,d) = g}} Ng/d\right) \\ &\le O\left(\sqrt{L} + \sum_{g \mid A+B} \sum_{{d\le \sqrt{L}, g \mid d}} Ng/d\right) \\ &= O\left(\sqrt{L} + \sum_{g \mid A+B} N\sum_{d\le \sqrt{L}/g} 1/d\right) \\ &\le O\left(\sqrt{L} + \sum_{g \mid A+B} N\sum_{d\le \sqrt{L}} 1/d\right) \\ &= O\left(\sqrt{L} + \sum_{g \mid A+B} N \log \sqrt{L}\right) \\ &= O\left(\sqrt{L} + N \log L \cdot d(A+B)\right) \end{aligned}

where d is the divisor count function.

Thus, the time complexity is O\left(\sqrt{L} + N \log L \cdot d(A+B)\right). Note that this is a pretty loose bound, but it still gives an idea of how fast this runs.

### Time Complexity:

O(\sqrt{L}+N \log L \cdot d(A+B)), where L = (A+B)N + AB + C, and d is the divisor count function.

3 Likes