# DIFFICULTY:

super-hard

# PREREQUISITES:

Extended Euclid, Diophanite Equation Solver

# PROBLEM:

Find the number of integer 3D points of the intersection between the plane ax + by + cz = d and the infinite prism x_1 \leq x \leq x_2, y_1\leq y \leq y_2.

# QUICK EXPLANATION:

Here problem is wrapping around with some geometry stuff but simply problem is to finding number of integer solution of equation ax + by + cz = d, where x_1 \leq x \leq x_2 and y_1 \leq y \leq y_2 and z is free. If we think about a box and a plane intersecting the box then here we need to find number of lattice points on the plane that is also inside the box. So what will be the condition for a point (x, y, z) to be inside a box whose 2 corner points are (x_1, y_1, z_1) and (x_2, y_2, z_2)? Condition will be x_1 \leq x \leq x_2, y_1 \leq y \leq y_2 and z_1 \leq z \leq z_2. Since this is a 3D stripe then, z_1 = -\infty and z_2 = +\infty. Now for satisfying the condition of point to be onto the plane also, so we basically need to find the number of integer tuple (x, y, z) such that ax + by + cz = d, x_1 \leq x \leq x_2 and y_1 \leq y \leq y_2. Now since ax + by + cz = d has 3 variables, here problem becomes a bit difficult. Same problem for diophanite equation is popular and classic problem.

# EXPLANATION:

So we can rewrite the given equation as follows:

gcd(a, c) \cdot f + by = d \rightarrow (i), where gcd(a, c) \cdot f = ax+cz \to (ii).

Here f is an integer.

For equation (i) we also know that y \in [y_1 , y_2], and for such y, we can also have a range of valid values of f. Let find out this below.

Let us find the values of f_g, y_g which satisfy the following:

gcd(a, c) f + by = gcd(a, b, c)

## How to compute?

We can get this by using extended euclid algorithm

Then, one of the solution of equation (i) is

f_0 = f_g \frac{d}{gcd(a, b, c)} and y_0 = y_g \frac{d}{gcd(a, b, c)}.

## Exception

If gcd(a, b, c) \nmid d, then there is no integer solution.

Now f_0 and g_0 is not the only solution. Other solution can be found by this arithmetic progression

f = f_0 + k \cdot \frac{b}{gcd( a, b, c )}

y = y_0 - k \cdot \frac{gcd( a, c )}{gcd( a, b, c )}.

Therefore, we get a range of values for y ( since y \in [y_1 : y_2]) as well as a range of solutions for f which will be an arithmetic progression \in [f_1, f_2] for some values f_1 and f_2. We can find f_1 and f_2 as well by the above calculation, which is not so difficult.

Suppose the first term of that arithmetic progression is a and difference between two terms is d and progression length is n. Now we can write the i th term of arithmetic progression:

T_i = u + i \cdot v, where f_1 \leq u + i \cdot v \leq f_2.

#### Now we have to solve our equation (ii) for every term of arithmetic progression.

Equation corresponding to T_i :

a \cdot x + c \cdot z = gcd(a, c)\cdot(u + i \cdot v) \rightarrow (iii)

where x_1 \leq x \leq x_2 and z is free.

Now problem is finding number of integer solutions of equation (iii) for all i.

Let x_g, z_g satisfy the following:

a \cdot x + c\cdot z = gcd(a, c)

This we can again find using extended euclid algorithm. Then, the solutions for equation (iii) will be:

x_0 = x_g\cdot (u + i \cdot v)

z_0 = z_g \cdot (u + i \cdot v)

#### Other solution can be found by the following formula:

x = x_0 + k \cdot \frac{c}{gcd(a, c)}

\implies x = x_g(u + iv) + k \cdot \frac{c}{gcd(a, c)}(replacing the value of x_0 = x_g(u + iv)).

\implies x = x_gu + x_gvi + k \cdot \frac{c}{gcd(a, c)}

\implies k = \frac{x - x_gu - x_gvi} {c / gcd(a, c )}

For i^{th} term, here lower bound is x_1. So minimum solution,

- k_{min_i} = \lceil{\frac{x_1 - x_gu - x_gvi}{c / gcd(a, c)}}\rceil \rightarrow (iv)

For i^{th} term, here upper bound is x_2. So maximum solution,

- k_{max_i} = \lfloor{\frac{x_2 - x_gu - x_gvi}{c / gcd(a, c)}}\rfloor \rightarrow (v)

So, number of solution of i^{th} term is (k_{max_i} - k_{min_i} + 1)

#### Now we need to sum this:

\sum{(k_{min_i} - k_{max_i} + 1)} = \sum{k_{min_i}} - \sum{k_{max_i}} + \sum 1

Now we will calculate \sum{k_{min_i}} and \sum{k_{max_i}} separately.

- \sum{k_{min_i}} and \sum{k_{max_i}} can be calculated in similar way.
- Here first observation is in equation (iv) numerator (x_1 - x_gu - x_gvi) is an arithmetic progression, where first term, p = x_1 - x_gu and difference between 2 term, q = -x_gv.
- Now problem coverts to calculating the floor sum of an arithmetic progression.

There can be at most 5 \cdot 10^5 terms in subtask1 and 10^9 terms in subtask2. So looping through all terms will be too slow. Let p is the first term of the arithmetic progression, q is the difference between 2 terms and n is the length of the progression.

Now we need to calculate floor sum:

\sum_{i = 0}^{n - 1} \lfloor \frac{p + iq}{r} \rfloor

\implies \sum_{i = 0}^{n - 1} \frac{(p + iq) - (p + iq)\ mod\ r}{r}

\implies \frac{1}{r} \sum_{i = 0}^{n - 1} (p + iq) - \frac{1}{r} \sum_{i = 0}^{n - 1} (p + iq)\ mod\ r

\implies \frac{\frac{n}{2}(2p + (n - 1)q)}{r} - \frac{1}{r} \sum_{i = 0}^{n - 1} (p + iq)\ mod\ r

### Now, here problem is to finding, S = \sum_{i = 0}^{n - 1} (p + iq)\ mod\ r

#### Letâ€™s try to solve this for subtask 1.

We will break the AP (aritmetic progression) into sq = \lfloor \sqrt n \rfloor number blocks of sq length and try to sum up each blocks. Letâ€™s take a view on i^{th}(0-based) block of AP:

- (p + sq \cdot i \cdot q), (p + (sq \cdot i + 1)q), (p + (sq \cdot i + 2)q).....(p + (sq \cdot i + sq - 1)q)

Here j^{th}(0-based) term of i^{th} block is

- p + (sq \cdot i + j)q = p + jq + (sq \cdot i \cdot q).

So here basically by adding (sq \cdot i \cdot q) to the j^{th} term of 0^{th} block we can get j^{th} term of i ^{th} block. Now we will take mod\ r into consideration.

Lets sum up the i^{th} block, that means:

- \sum_{j = 0}^{sq - 1}(p + jq + (sq \cdot i \cdot q))\ mod\ r

\implies \sum_{j = 0}^{sq - 1}((p + jq)\ mod\ r + (sq \cdot i \cdot q)\ mod\ r)\ mod\ r

Now we will use this observation that by adding (sq \cdot i \cdot q) to the j^{th} term of 0^{th} block we can get j^{th} term of i ^{th} block.

Letâ€™s sort the 0^{th} block on the basis of (p + jq)\ mod\ r. Let \{s_1, s_2, s_3, ...., s_{sq - 1}\} is the sorted sequence, where s_j < r.

#### To sum up i^{th} block we need to calculate:

- \sum_{j = 0}^{sq - 1}(s_j + (sq \cdot i \cdot q)\ mod\ r)\ mod\ r

\implies \sum_{j = 0}^{sq - 1}(s_j + C)\ mod\ r (let C = (sq \cdot i \cdot q)\ mod\ r, here C < r)

\implies \sum_{j = 0}^{l}(s_j + C)\ mod\ r + \sum_{j = l + 1}^{sq - 1}(s_j + C)\ mod\ r (here sequence is broken into two parts. In first part s_j + C < r where 0 \leq j \leq l and in second part r \leq s_j + C < 2r, where l + 1 \leq j \leq sq - 1)

\implies \sum_{j = 0}^{l}(s_j + C) + \sum_{j = l + 1}^{sq - 1}(s_j + C - r)

\implies \sum_{j = 0}^{l}(s_j + C) + \sum_{j = l + 1}^{sq - 1}(s_j + C) - \sum_{j = l + 1}^{sq - 1}r

\implies \sum_{j = 0}^{sq - 1}(s_j + C) - r(sq - l - 1)

So, by doing a binary search we can get our l. So to solve each block we need to do a binary search on a sq length sorted sequence. There are \frac{n}{sq} = sq blocks. Complexity of solving each test case is O(\sqrt n log_2(\sqrt n)). So total time complexity for subtask1 is O(T \cdot \sqrt n log_2(\sqrt n))

### Solving subtask 2

Now for subtask 2 we will try to find floor sum of AP in log_2(n), which is described briefly in the following blog with all kind of variants. So total time complexity of subtask2 is O(T \cdot log_2(n))(constant factor is too high)

In this solution we need to be concerned about some overflow issues because the first term of the AP might not be fit in long long int. So we may need to use 128 bit data type. And also we need to concern about floor sum of AP when terms are both negative and positive. We need to handle this negative and positive terms separately(This depends on how you implement the solution)