Pave the Parallelepiped
Contest: Codeforces Round 497 (Div. 1)
Difficulty rating: 2400
Tags: bitmasks, brute force, combinatorics, math, number theory

You are given a rectangular parallelepiped with sides of positive integer lengths $$$A$$$, $$$B$$$ and $$$C$$$.

Find the number of different groups of three integers ($$$a$$$, $$$b$$$, $$$c$$$) such that $$$1\leq a\leq b\leq c$$$ and parallelepiped $$$A\times B\times C$$$ can be paved with parallelepipeds $$$a\times b\times c$$$. Note, that all small parallelepipeds have to be rotated in the same direction.

For example, parallelepiped $$$1\times 5\times 6$$$ can be divided into parallelepipeds $$$1\times 3\times 5$$$, but can not be divided into parallelepipeds $$$1\times 2\times 3$$$.

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

Each of the next $$$t$$$ lines contains three integers $$$A$$$, $$$B$$$ and $$$C$$$ ($$$1 \leq A, B, C \leq 10^5$$$) — the sizes of the parallelepiped.

Output format:
For each test case, print the number of different groups of three points that satisfy all given conditions.

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

Note:
In the first test case, rectangular parallelepiped $$$(1, 1, 1)$$$ can be only divided into rectangular parallelepiped with sizes $$$(1, 1, 1)$$$.

In the second test case, rectangular parallelepiped $$$(1, 6, 1)$$$ can be divided into rectangular parallelepipeds with sizes $$$(1, 1, 1)$$$, $$$(1, 1, 2)$$$, $$$(1, 1, 3)$$$ and $$$(1, 1, 6)$$$.

In the third test case, rectangular parallelepiped $$$(2, 2, 2)$$$ can be divided into rectangular parallelepipeds with sizes $$$(1, 1, 1)$$$, $$$(1, 1, 2)$$$, $$$(1, 2, 2)$$$ and $$$(2, 2, 2)$$$.

Example input:
4
1 1 1
1 6 1
2 2 2
100 100 100

Example output:
1
4
4
165

Editorial:
First solution.
First, for every natural number up to $$$10^5$$$ we count its number of divisors in $$$O(\sqrt{n})$$$. Also for every unordered set of $$$3$$$ masks $$$(m_1, m_2, m_3)$$$ of length $$$3$$$ we check if there is а way to enumerate them in such a way that $$$1 \in m_1$$$, $$$2 \in m_2$$$ and $$$3 \in m_3$$$. We will call such sets acceptable.
Now let's consider two parallelepipeds. For each dimension of the second parallelepiped let's construct a mask of length $$$3$$$ which contains the numbers of the dimensions of the first parallelepiped for which the length of the first parallelepiped along this dimension is divisible by the length of the second parallelepiped along the chosen dimension. Now these three masks form an acceptable set iff we can pave the first parallelepiped with the second one.
Now for a given parallelepiped let's calculate for every mask of length $$$3$$$ the number of possible lengths of the second parallelepiped which would produce this mask. We can do this by taking the GCD of the lengths of the first parallelepiped along the dimensions whose numbers are in the mask, and subtracting from it the calculated numbers for every submask.
Now let's iterate over acceptable sets of masks. For each different mask from the set which is included into the set $$$k$$$ times we need to calculate the number of ways to take $$$k$$$ unordered lengths which produce this mask, and multiply these numbers. The sum of these numbers is the answers to the query.
So for every query we need $$$O \left( 2^{m^2} \right)$$$ operations, where $$$m = 3$$$ is the number of dimensions of the parallelepiped.
Second solution.
First, for every natural number up to $$$10^5$$$ we count its number of divisors in $$$O(\sqrt{n})$$$.
Then for every query for every subset of numbers in it we keep their GCD and the number of its divisors. So for every subset of this three numbers we know the number of their common divisors.
Let's look at the parallelepiped $$$(a, b, c)$$$. The way we orient it with respect to the large parallelepiped is determined by a permutation of size $$$3$$$ — that is, which dimension would correspond to every dimension in the large one. Using the inclusion-exclusion principle on this permutations we can count how many there are such parallelepipeds (considering the orientation) that we can orient some way to then pave the large parallelepiped with it. Namely, we fix the set of permutations for which our parallelepiped shall satisfy. Then for every side of the small parallelepiped we know which sides of the large one it shall divide. To find the number of such sides of the small one we shall take the number of common divisors of the corresponding sides of the large one. Now to find the number of such small parallelepipeds we must multiply the three resultant numbers.
In such way every satisfying this criteria parallelepiped (not considering the orientation) with three different side lengths was counted $$$6$$$ times, with two different lengths was counted $$$3$$$ times, with one different length was counted $$$1$$$ time. But it won't be difficult for us to use the same approach in counting such parallelepipeds, but with no less than two same side lengths: let's say the first and the second. To do this when we fix which permutations this parallelepiped shall satisfy we should just add the condition that its first and second side lengths must be equal, this means they both must divide both of the sets corresponding to them, so instead of this two sets we must take their union.
Let's add the resultant number multiplied by three to the answer. Now every parallelepiped with three different side length is still counted $$$6$$$ times, with two different is now counted also $$$6$$$ times, and with one different is counted $$$4$$$ times. The number of satisfying parallelepipeds with equal sides is just the number of common divisors of all the sides of the large parallelepiped. Let's add it multiplied by two, and now every needed parallelepiped is counted $$$6$$$ times. We divide this number by $$$6$$$ and get the answer.
So for every query we need $$$O \left( p(m) \cdot 2^{m!} \cdot m \right)$$$ operations, where $$$p(m)$$$ is the number of partitions of $$$m$$$, and $$$m = 3$$$ is the number of dimensions of the parallelepiped.