English · Original
Chinese · Translation
Formal · Original
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
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
For each test case, print the number of different groups of three points that satisfy all given conditions.
[samples]
## 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)$.
[{"iden":"statement","content":"给你一个边长为正整数 $A$、$B$ 和 $C$ 的长方体。\n\n求满足 $1 lt.eq a lt.eq b lt.eq c$ 的不同三元组 $(a, b, c)$ 的数量，使得尺寸为 $A \\times B \\times C$ 的长方体可以被若干个尺寸为 $a \\times b \\times c$ 的小长方体完全铺满。注意，所有小长方体必须以相同的方向旋转。\n\n例如，尺寸为 $1 \\times 5 \\times 6$ 的长方体可以被划分为尺寸为 $1 \\times 3 \\times 5$ 的长方体，但不能被划分为尺寸为 $1 \\times 2 \\times 3$ 的长方体。\n\n第一行包含一个整数 $t$ ($1 lt.eq t lt.eq 10^5$) —— 测试用例的数量。\n\n接下来的 $t$ 行每行包含三个整数 $A$、$B$ 和 $C$ ($1 lt.eq A, B, C lt.eq 10^5$) —— 长方体的尺寸。\n\n对于每个测试用例，输出满足所有给定条件的不同三元组的数量。\n\n在第一个测试用例中，长方体 $(1, 1, 1)$ 只能被划分为尺寸为 $(1, 1, 1)$ 的长方体。\n\n在第二个测试用例中，长方体 $(1, 6, 1)$ 可以被划分为尺寸为 $(1, 1, 1)$、$(1, 1, 2)$、$(1, 1, 3)$ 和 $(1, 1, 6)$ 的长方体。\n\n在第三个测试用例中，长方体 $(2, 2, 2)$ 可以被划分为尺寸为 $(1, 1, 1)$、$(1, 1, 2)$、$(1, 2, 2)$ 和 $(2, 2, 2)$ 的长方体。 "},{"iden":"input","content":"第一行包含一个整数 $t$ ($1 lt.eq t lt.eq 10^5$) —— 测试用例的数量。接下来的 $t$ 行每行包含三个整数 $A$、$B$ 和 $C$ ($1 lt.eq A, B, C lt.eq 10^5$) —— 长方体的尺寸。"},{"iden":"output","content":"对于每个测试用例，输出满足所有给定条件的不同三元组的数量。"},{"iden":"note","content":"在第一个测试用例中，长方体 $(1, 1, 1)$ 只能被划分为尺寸为 $(1, 1, 1)$ 的长方体。在第二个测试用例中，长方体 $(1, 6, 1)$ 可以被划分为尺寸为 $(1, 1, 1)$、$(1, 1, 2)$、$(1, 1, 3)$ 和 $(1, 1, 6)$ 的长方体。在第三个测试用例中，长方体 $(2, 2, 2)$ 可以被划分为尺寸为 $(1, 1, 1)$、$(1, 1, 2)$、$(1, 2, 2)$ 和 $(2, 2, 2)$ 的长方体。 "}]}
**Definitions**
Let $ t \in \mathbb{Z} $ be the number of test cases.
Let $ T = \{(A_k, B_k, C_k) \mid k \in \{1, \dots, t\}\} $ be the set of test cases, where for each $ k $:
- $ A_k, B_k, C_k \in \mathbb{Z}^+ $ denote the side lengths of the large rectangular parallelepiped.
Let $ \mathcal{P} $ be the set of all ordered triples $ (a, b, c) \in \mathbb{Z}^3 $ such that $ 1 \le a \le b \le c $.
**Constraints**
1. $ 1 \le t \le 10^5 $
2. For each $ k \in \{1, \dots, t\} $:
- $ 1 \le A_k, B_k, C_k \le 10^5 $
**Objective**
For each test case $ (A, B, C) $, compute the number of triples $ (a, b, c) \in \mathcal{P} $ such that:
$$
a \mid A,\quad b \mid B,\quad c \mid C \quad \text{or any permutation of } (a,b,c) \text{ divides } (A,B,C) \text{ in some order}.
$$
**Clarification (from problem context)**
The small parallelepiped $ a \times b \times c $ must tile the large one $ A \times B \times C $ with all small parallelepipeds oriented identically (i.e., no rotation among small blocks; the entire tiling uses the same alignment). This implies that $ (a,b,c) $ must be a *direct divisor triple*: there exists a permutation $ \sigma \in S_3 $ such that:
$$
a \mid A_{\sigma(1)}, \quad b \mid A_{\sigma(2)}, \quad c \mid A_{\sigma(3)},
$$
where $ (A_{\sigma(1)}, A_{\sigma(2)}, A_{\sigma(3)}) $ is a sorted version of $ (A,B,C) $. But since $ a \le b \le c $, and tiling requires alignment, the only valid configuration is when $ (a,b,c) $ divides $ (A,B,C) $ **after sorting both triples in non-decreasing order**.
Thus, define:
Let $ (A', B', C') $ be the sorted version of $ (A, B, C) $, i.e., $ A' \le B' \le C' $.
Then $ (a, b, c) \in \mathcal{P} $ is valid if and only if:
$$
a \mid A', \quad b \mid B', \quad c \mid C'.
$$
**Final Objective**
For each test case $ (A, B, C) $, let $ (A', B', C') = \text{sort}(A, B, C) $.
Compute:
$$
\left| \left\{ (a, b, c) \in \mathbb{Z}^3 \,\middle|\, 1 \le a \le b \le c,\ a \mid A',\ b \mid B',\ c \mid C' \right\} \right|
$$
API Response (JSON)
{
"problem": {
"name": "B. Pave the Parallelepiped",
"description": {
"content": "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 ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF1007B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "You are given a rectangular parallelepiped with sides of positive integer lengths $A$, $B$ and $C$.\n\nFind the number of different groups of three integers ($a$, $b$, $c$) such that $1\\leq a\\leq b\\leq ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "[{\"iden\":\"statement\",\"content\":\"给你一个边长为正整数 $A$、$B$ 和 $C$ 的长方体。\\n\\n求满足 $1 lt.eq a lt.eq b lt.eq c$ 的不同三元组 $(a, b, c)$ 的数量，使得尺寸为 $A \\\\times B \\\\times C$ 的长方体可以被若干个尺寸为 $a \\\\times b \\\\times c$ 的小长方体完全铺满。注...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ t \\in \\mathbb{Z} $ be the number of test cases. \nLet $ T = \\{(A_k, B_k, C_k) \\mid k \\in \\{1, \\dots, t\\}\\} $ be the set of test cases, where for each $ k $: \n- $ A_k, B_k, C_k...",
"is_translate": false,
"language": "Formal"
}
]
}