Boundary
Contest: SWERC 2021-2022 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Tags: brute force, math

Bethany would like to tile her bathroom. The bathroom has width $$$w$$$ centimeters and length $$$l$$$ centimeters. If Bethany simply used the basic tiles of size $$$1 \times 1$$$ centimeters, she would use $$$w \cdot l$$$ of them.

However, she has something different in mind.

- On the interior of the floor she wants to use the $$$1 \times 1$$$ tiles. She needs exactly $$$(w-2) \cdot (l-2)$$$ of these.
- On the floor boundary she wants to use tiles of size $$$1 \times a$$$ for some positive integer $$$a$$$. The tiles can also be rotated by $$$90$$$ degrees.

For which values of $$$a$$$ can Bethany tile the bathroom floor as described? Note that $$$a$$$ can also be $$$1$$$.

Input format:
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1\le t\le 100$$$) — the number of test cases. The descriptions of the $$$t$$$ test cases follow.

Each test case consist of a single line, which contains two integers $$$w$$$, $$$l$$$ ($$$3 \leq w, l \leq 10^{9}$$$) — the dimensions of the bathroom.

Output format:
For each test case, print an integer $$$k$$$ ($$$0\le k$$$) — the number of valid values of $$$a$$$ for the given test case — followed by $$$k$$$ integers $$$a_1, a_2,\dots, a_k$$$ ($$$1\le a_i$$$) — the valid values of $$$a$$$. The values $$$a_1, a_2, \dots, a_k$$$ have to be sorted from smallest to largest.

It is guaranteed that under the problem constraints, the output contains at most $$$200\,000$$$ integers.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the bathroom is $$$3$$$ centimeters wide and $$$5$$$ centimeters long. There are three values of $$$a$$$ such that Bethany can tile the floor as described in the statement, namely $$$a=1$$$, $$$a=2$$$ and $$$a=3$$$. The three tilings are represented in the following pictures.

Example input:
3
3 5
12 12
314159265 358979323

Example output:
3 1 2 3
3 1 2 11
2 1 2

Editorial:
First, observe that we can tile any rectangle with tiles of size $$$1 \times 1$$$. From now on, we will consider a fixed $$$a > 1$$$.
Let's investigate what happens in the corners of the rectangle. Each corner is covered either by a tile that is placed horizontally, or by a tile that is placed vertically. Below is an example of one of $$$2^4 = 16$$$ possibilities, with the corner tiles in gray.
Once we place those tiles (up to $$$4$$$, fewer if the tile length is greater than $$$\frac{w}{2}$$$ or $$$\frac{l}{2}$$$) the positions of the rest are uniquely determined.
We can now put four constraints on the value of $$$a$$$, one for each side of the rectangle. These constraints are of form $$$a \mid w - x$$$ or $$$a \mid l - x$$$, where $$$\mid$$$ is the "divides without remainde" relation, and $$$x$$$ is the number of positions on that side that are covered by a tile placed in a perpendicular direction, e.g. a vertical tile on a horizontal side. Clearly, this can only happen in the corners of the rectangle, hence $$$x$$$ is between $$$0$$$ and $$$2$$$ for all sides.
In the above figure, the top side yields the constraint $$$a \mid w - 0$$$, the bottom one $$$a \mid w - 2$$$, and both the left and right sides $$$a \mid l - 1$$$. Put together, we have a necessary condition $$$a \mid \gcd(w - 0, \, w - 2, \, l - 1, \, l - 1)$$$, where $$$\gcd$$$ is the greatest common divisor. Clearly, the condition is also sufficient, i.e. for an $$$a$$$ fulfilling this divisibility there is a rectangle tiling.
To summarise, we consider all $$$16$$$ possibilities for the tile orientations in the corners, find the $$$\gcd$$$ of the constraints using Euclidean algorithm, and then compute its divisiors by a trial division. Finally, we return the sorted set of all the divisors. The total time complexity is $$$\mathcal O(\sqrt {\min(w, \, l)})$$$ per test case, dominated by the trial division.
Note that some of the $$$16$$$ cases are the same up to mirroring or rotation, and some are clearly impossible. Hence we only need to factor the following values:
• $$$\gcd(w - 1, \, l - 1)$$$
• $$$\gcd(w, \, l - 2)$$$
• $$$\gcd(w - 2, \, l)$$$
• $$$\gcd(w - 1, \, l - 2, \, l)$$$
• $$$\gcd(w - 2, \, w, \, l - 1)$$$
The last two can only be $$$1$$$ or $$$2$$$, and if they are both $$$1$$$, this implies that one of the first three $$$\gcd$$$s is divisible by $$$2$$$. Therefore $$$a = 2$$$ is always a solution — we can simply insert it to the solution set, and only compute and factor the first three $$$\gcd$$$s. This does not change the asymptotic time complexity, nevertheless it is a useful optimisation.