Constructing tetrahedrons

Submit solution

Points: 25 (partial)
Time limit: 1.0s
Python 3 3.0s
Memory limit: 256M

Problem type

We want to construct a tetrahedron (a triangular pyramid) in such a way that one of its vertices coincides with the origin of the 3D frame, and each one of the other three vertices belongs to one of the three axes of the 3D frame.

Formally, let A, B, C, D be the 4 vertices of the tetrahedron, then : \(A = (0,0,0)\), \(B = (X,0,0)\), \(C = (0,Y,0)\) and \(D = (0,0,Z)\), where \(X\), \(Y\) and \(Z\) are positive integer numbers. When \(X\) divides \(Y\) and \(Y\) divides \(Z\) the tetrahedron is called beautiful.

You have an array A of integer numbers, you can chose any three elements \(A_i, A_j, A_k\), \(i < j < k \) as dimensions of the tetrahedron (values of \(X,Y,Z\) Respectively).

How many beautiful tetrahedrons you can construct ?

Input Specification

Input starts with a line containing one integer \(N\) (\(1 \leq N \leq 1500\)) Then follows \(N\) integers denoting the array \(A\) (\( 1 \leq A_i \leq 10^9\)).

Output Specification

Output one integer : the number of beautiful tetrahedrons.


  • \(N \leq 100\) (\(30\) Points).
  • \(N \leq 1500\) (\(70\) Points).

Sample Input

1 2 3 4 5

Sample Output



There are no comments at the moment.