{"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 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**.\n\nFor 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$.\n\n## Input\n\nThe first line contains a single integer $t$ ($1 \\leq t \\leq 10^5$) — the number of test cases.\n\nEach 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.\n\n## Output\n\nFor each test case, print the number of different groups of three points that satisfy all given conditions.\n\n[samples]\n\n## Note\n\nIn the first test case, rectangular parallelepiped $(1, 1, 1)$ can be only divided into rectangular parallelepiped with sizes $(1, 1, 1)$.\n\nIn 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)$.\n\nIn 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)$.","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$ 的小长方体完全铺满。注意，所有小长方体 *必须朝向相同*。\\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)$ 的长方体。 \"}]}","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 rectangular parallelepiped.\n\nLet $ \\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 $.\n\n**Constraints**  \n1. $ 1 \\le t \\le 10^5 $  \n2. For each test case $ k $: $ 1 \\le A_k, B_k, C_k \\le 10^5 $\n\n**Objective**  \nFor each test case $ k $, compute the number of triples $ (a, b, c) \\in \\mathcal{P} $ such that:  \n$$\na \\mid A_k,\\quad b \\mid B_k,\\quad c \\mid C_k\n$$  \n**or**  \n$$\na \\mid A_k,\\quad b \\mid C_k,\\quad c \\mid B_k\n$$  \n**or**  \n$$\na \\mid B_k,\\quad b \\mid A_k,\\quad c \\mid C_k\n$$  \n**or**  \n$$\na \\mid B_k,\\quad b \\mid C_k,\\quad c \\mid A_k\n$$  \n**or**  \n$$\na \\mid C_k,\\quad b \\mid A_k,\\quad c \\mid B_k\n$$  \n**or**  \n$$\na \\mid C_k,\\quad b \\mid B_k,\\quad c \\mid A_k\n$$  \n\nThat 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.\n\nBut 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.\n\nThus, the condition is:  \nThere exists a permutation $ \\sigma \\in S_3 $ such that:  \n$$\na \\mid X_{\\sigma(1)},\\quad b \\mid X_{\\sigma(2)},\\quad c \\mid X_{\\sigma(3)}\n$$  \nwhere $ X = (A_k, B_k, C_k) $.\n\nHence, the objective is:  \nFor each test case $ k $, compute:  \n$$\n\\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|\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1008D","tags":["math","number theory"],"sample_group":[["4\n1 1 1\n1 6 1\n2 2 2\n100 100 100","1\n4\n4\n165"]],"created_at":"2026-03-03 11:00:39"}}