Divisors and Table
Contest: Educational Codeforces Round 142 (Rated for Div. 2)
Difficulty rating: 2400
Tags: brute force, dfs and similar, dp, number theory

You are given an $$$n \times n$$$ multiplication table and a positive integer $$$m = m_1 \cdot m_2$$$. A $$$n \times n$$$ multiplication table is a table with $$$n$$$ rows and $$$n$$$ columns numbered from $$$1$$$ to $$$n$$$, where $$$a_{i, j} = i \cdot j$$$.

For each divisor $$$d$$$ of $$$m$$$, check: does $$$d$$$ occur in the table at least once, and if it does, what is the minimum row that contains $$$d$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10$$$) — the number of test cases.

The first and only line of each test case contains three integers $$$n$$$, $$$m_1$$$ and $$$m_2$$$ ($$$1 \le n \le 10^9$$$; $$$1 \le m_1, m_2 \le 10^9$$$) — the size of the multiplication table and the integer $$$m$$$ represented as $$$m_1 \cdot m_2$$$.

Output format:
For each test case, let $$$d_1, d_2, \dots, d_k$$$ be all divisors of $$$m$$$ sorted in the increasing order. And let $$$a_1, a_2, \dots, a_k$$$ be an array of answers, where $$$a_i$$$ is equal to the minimum row index where divisor $$$d_i$$$ occurs, or $$$0$$$, if there is no such row.

Since array $$$a$$$ may be large, first, print an integer $$$s$$$ — the number of divisors of $$$m$$$ that are present in the $$$n \times n$$$ table. Next, print a single value $$$X = a_1 \oplus a_2 \oplus \dots \oplus a_k$$$, where $$$\oplus$$$ denotes the bitwise XOR operation.

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

Note:
In the first test case, $$$m = 72 \cdot 1 = 72$$$ and has $$$12$$$ divisors $$$[1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72]$$$. The $$$3 \times 3$$$ multiplication table looks like that:

123112322463369

For each divisor of $$$m$$$ that is present in the table, the position with minimum row index is marked. So the array of answers $$$a$$$ is equal to $$$[1, 1, 1, 2, 2, 0, 3, 0, 0, 0, 0, 0]$$$. There are only $$$6$$$ non-zero values, and xor of $$$a$$$ is equal to $$$2$$$.

In the second test case, $$$m = 10 \cdot 15 = 150$$$ and has $$$12$$$ divisors $$$[1, 2, 3, 5, 6, 10, 15, 25, 30, 50, 75, 150]$$$. All divisors except $$$75$$$ and $$$150$$$ are present in the $$$10 \times 10$$$ table. Array $$$a$$$ $$$=$$$ $$$[1, 1, 1, 1, 1, 1, 3, 5, 3, 5, 0, 0]$$$. There are $$$10$$$ non-zero values, and xor of $$$a$$$ is equal to $$$0$$$.

In the third test case, $$$m = 1 \cdot 210 = 210$$$ and has $$$16$$$ divisors $$$[1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210]$$$. The $$$6 \times 6$$$ table with marked divisors is shown below:

1234561123456224681012336912151844812162024551015202530661218243036

Array $$$a$$$ $$$=$$$ $$$[1, 1, 1, 1, 1, 0, 2, 0, 3, 0, 5, 0, 0, 0, 0, 0]$$$. There are $$$8$$$ non-zero values, and xor of $$$a$$$ is equal to $$$5$$$.

Example input:
3
3 72 1
10 10 15
6 1 210

Example output:
6 2
10 0
8 5

Editorial:
Firstly, let's factorize $$$m$$$. Since $$$m = m_1 \cdot m_2$$$ we can factorize $$$m_1$$$ and $$$m_2$$$ separately and then "unite" divisors. For example, use can get canonical representations of $$$m_1 = p_1^{f_1} p_2^{f_2} \dots p_k^{f_k}$$$ and $$$m_2 = p_1^{g_1} p_2^{g_2} \dots p_k^{g_k}$$$ to get canonical representation of $$$m = p_1^{f_1 + g_1} p_2^{f_2 + g_2} \dots p_k^{f_k + g_k}$$$ and then use it to generate all divisors of $$$m$$$.
Let's estimate the number of divisors $$$divs(m)$$$. It's convenient for our purposes to estimate it as $$$O(m^{\frac{1}{3}})$$$. More precisely, there are at most $$$105\,000$$$ divisors for $$$m \le 10^{18}$$$ (search "Highly Composite Numbers" for more info).
How to calculate the answer $$$a_i$$$ for each divisor $$$d$$$? There are two ways.
The intended solution: for each $$$d$$$ we are searching for the minimum $$$x$$$ that $$$d = x y$$$ and $$$y \le n$$$. Since $$$d$$$ is fixed, the minimum $$$x$$$ means the maximum $$$y \le n$$$. So let's find $$$y$$$ instead. In other words, for each $$$d$$$ we need to find the maximum $$$y$$$ such that $$$y$$$ divides $$$d$$$ and $$$y \le n$$$. We can do it efficiently with $$$dp$$$ on divisors.
Let $$$dp[d]$$$ be the maximum $$$y$$$ that is a divisor of $$$d$$$ and $$$y \le n$$$. If $$$d \le n$$$ then, obviously, $$$dp[d] = d$$$. Otherwise, we know that we are searching $$$y < d$$$.
Let say that $$$p_1, p_2, \dots, p_k$$$ are the prime divisors of the initial number $$$m$$$. Since $$$y$$$ is a divisor of $$$d$$$ and $$$y < d$$$ then exists some $$$p_i$$$ among the set of prime divisors such that $$$y$$$ is a divisor of $$$\frac{d}{p_i}$$$ as well. So, instead of brute search, it's enough to take a value $$$dp[\frac{d}{p_i}]$$$.
In other words, if $$$d > n$$$ we can calculate $$$dp[d] = \max\limits_{p_i | d}{dp[\frac{d}{p_i}]}$$$.
Ok, now we know value $$$dp[d]$$$ for each divisor $$$d$$$. Since we found the maximum $$$y \le n$$$, the last step is to calculate the desired $$$x = \frac{d}{dp[d]}$$$ and if $$$x \le n$$$ we found the answer $$$a_i$$$, otherwise ($$$x > n$$$) it means that $$$d$$$ is not presented $$$n \times n$$$ table and $$$a_i = 0$$$.
The total complexity is $$$O(\sqrt{m_1 + m_2} + divs(m) \cdot z(m) \cdot \log(divs(m)))$$$ per test, where $$$divs(m)$$$ is the number of divisors of $$$m$$$ ($$$divs(m) \le 105\,000$$$) and $$$z(m)$$$ is the number of prime divisor of $$$m$$$ ($$$z(m) \le 15$$$). Note that complexity is quite high, so you should write it at least a little accurate, for example store $$$dp[d]$$$ in an array, not map, and search position of $$$dp[\frac{d}{p_i}]$$$ with $$$lower\_bound()$$$.
There is also a way to get rid of extra $$$\log(divs(m))$$$ factor if you iterate through $$$dp$$$ is a smart way.
The alternative solution (faster, easier, unproven): Let's generate a list of all divisors of $$$m$$$ as $$$d_1, d_2, \dots, d_l$$$ in the increasing order. For some divisor $$$d_i$$$ we are searching the minimum $$$x$$$ that is a divisor of $$$d_i$$$ and $$$\frac{d_i}{x} \le n$$$. It means that $$$x \ge \left\lceil \frac{d_i}{n} \right\rceil$$$.
So let's just find the first position $$$j$$$ such that $$$d_j \ge \left\lceil \frac{d_i}{n} \right\rceil$$$ with $$$lower\_bound$$$ and start iterating from $$$j$$$ onward searching the first $$$d_j$$$ that is a divisor of $$$d_i$$$. The found $$$d_j$$$ would be the minimum $$$x$$$ we need.
It looks like, in average, we will find the correct $$$d_j$$$ quite fast, or we'll break when $$$d_j > n$$$.