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.
For each test case $ k \in \{1, \dots, t\} $, let $ (A_k, B_k, C_k) \in \mathbb{Z}_{>0}^3 $ denote the dimensions of the large rectangular parallelepiped.
Let $ \mathcal{P} $ be the set of all ordered triples $ (a, b, c) \in \mathbb{Z}_{>0}^3 $ such that $ 1 \le a \le b \le c $.
**Constraints**
1. $ 1 \le t \le 10^5 $
2. For each test case $ k $: $ 1 \le A_k, B_k, C_k \le 10^5 $
**Objective**
For each test case $ k $, compute the number of triples $ (a, b, c) \in \mathcal{P} $ such that:
$$
a \mid A_k,\quad b \mid B_k,\quad c \mid C_k
$$
**or**
$$
a \mid A_k,\quad b \mid C_k,\quad c \mid B_k
$$
**or**
$$
a \mid B_k,\quad b \mid A_k,\quad c \mid C_k
$$
**or**
$$
a \mid B_k,\quad b \mid C_k,\quad c \mid A_k
$$
**or**
$$
a \mid C_k,\quad b \mid A_k,\quad c \mid B_k
$$
**or**
$$
a \mid C_k,\quad b \mid B_k,\quad c \mid A_k
$$
That is, $ (a, b, c) $ must tile $ (A_k, B_k, C_k) $ under **a fixed orientation** of the small parallelepiped — meaning the dimensions $ a, b, c $ must align **in some permutation** with $ A_k, B_k, C_k $, and each small dimension must divide the corresponding large dimension.
But note: the problem requires $ a \le b \le c $, and the small parallelepipeds are **not rotated relative to each other**, but the entire set may be aligned with any permutation of the large box’s axes.
Thus, the condition is:
There exists a permutation $ \sigma \in S_3 $ such that:
$$
a \mid X_{\sigma(1)},\quad b \mid X_{\sigma(2)},\quad c \mid X_{\sigma(3)}
$$
where $ X = (A_k, B_k, C_k) $.
Hence, the objective is:
For each test case $ k $, compute:
$$
\left| \left\{ (a,b,c) \in \mathcal{P} \;\middle|\; \exists \sigma \in S_3 \text{ s.t. } a \mid X_{\sigma(1)},\ b \mid X_{\sigma(2)},\ c \mid X_{\sigma(3)} \right\} \right|
$$
API Response (JSON)
{
"problem": {
"name": "D. 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": "CF1008D"
},
"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. \nFor each test case $ k \\in \\{1, \\dots, t\\} $, let $ (A_k, B_k, C_k) \\in \\mathbb{Z}_{>0}^3 $ denote the dimensions of the large...",
"is_translate": false,
"language": "Formal"
}
]
}