Pave the Parallelepiped (Codeforces 1008D)
Tags: 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: 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.

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)$$$. 

Sample Inputs:
4
1 1 1
1 6 1
2 2 2
100 100 100

Sample Outputs:
1
4
4
165

Solution (Python):
from math import gcd
N = 100001
d = [0 for i in range(N)]
for i in range(1, N):
    for j in range(i, N, i):
        d[j] += 1
n = int(input())
for _ in range(n):
    (a, b, c) = map(int, input().split())
    (A, B, C) = (d[a], d[b], d[c])
    (AB, BC, CA) = (d[gcd(a, b)], d[gcd(b, c)], d[gcd(c, a)])
    ABC = d[gcd(gcd(a, b), c)]
    print(A * B * C - AB * BC * CA + ABC * (AB * BC + BC * CA + CA * AB) - A * BC * (BC - 1) // 2 - B * CA * (CA - 1) // 2 - C * AB * (AB - 1) // 2 - ABC * (ABC + 1) * (AB + BC + CA) // 2 + ABC * (ABC + 1) * (ABC + 2) // 6)

Solution (Python):
from math import gcd
N = 100001
d = [0 for i in range(N)]
for i in range(1, N):
    for j in range(i, N, i):
        d[j] += 1
n = int(input())
for _ in range(n):
    (a, b, c) = map(int, input().split())
    (A, B, C) = (d[a], d[b], d[c])
    (AB, BC, CA) = (d[gcd(a, b)], d[gcd(b, c)], d[gcd(c, a)])
    ABC = d[gcd(gcd(a, b), c)]
    print(A * B * C - AB * BC * CA + ABC * (AB * BC + BC * CA + CA * AB) - A * BC * (BC - 1) // 2 - B * CA * (CA - 1) // 2 - C * AB * (AB - 1) // 2 - ABC * (ABC + 1) * (AB + BC + CA) // 2 + ABC * (ABC + 1) * (ABC + 2) // 6)

Solution (Python):
from math import gcd
N = 100001
d = [0 for i in range(N)]
for i in range(1, N):
    for j in range(i, N, i):
        d[j] += 1
n = int(input())
for _ in range(n):
    (a, b, c) = map(int, input().split())
    (A, B, C) = (d[a], d[b], d[c])
    (AB, BC, CA) = (d[gcd(a, b)], d[gcd(b, c)], d[gcd(c, a)])
    ABC = d[gcd(gcd(a, b), c)]
    print(A * B * C - AB * BC * CA + ABC * (AB * BC + BC * CA + CA * AB) - A * BC * (BC - 1) // 2 - B * CA * (CA - 1) // 2 - C * AB * (AB - 1) // 2 - ABC * (ABC + 1) * (AB + BC + CA) // 2 + ABC * (ABC + 1) * (ABC + 2) // 6)