All Tracks Math Number Theory Primality Tests Problem

Perfect Cubes
/

Hash function, Mathematics, Meet In the Middle, Number Theory, Primality test, Prime Factorization

Problem
Editorial
Analytics

You have \(N\) numbers, \(X_{1}, X_{2}, X_{3}, ... , X_{N}\). How many ways you can choose 4 numbers such that their product is a perfect cube. Formally, how many ways you can choose 4 integeres \(a, b, c, d\) and \(1 <= a < b < c < d <= N\) such that product of \(X_{a} , X_{b}, X_{c}, X_{d}\) is a perfect cube.

A number \(Z\) is said to be a perfect cube if there exists an integer \(Y \) such that \(Z = Y^3\).

Since the numbers can be quite large, so instead of giving a number directly, you will be given \(K_{i}\)  integers, \(P_{1}, P_{2}, P_{3}, ... , P_{K}\). Formally, each number \(X_{i}\)  is a product of \(P_{1}, P_{2}, P_{3}, ... , P_{K}\).

Input Format

First line will contain \(N\)
Each of next \(N\) lines will start with \(K_{i}\). Next \(K_{i}\) integers \(P_{1}, P_{2}, P_{3}, ... , P_{K}\)  will be sperated by a space.

\(4 <= N <= 1000\)

\(1 <= K_{i} <= 100\)

\(1 <= P_{j} <= 500\)

Ouput Format

Print only one integer, which is many ways you can choose 4 numbers such that their product is a perfect cube.

 

Addition Information

For 20 points: \(4 <= N <= 50\)\(1 <= K_{i} <= 25\)\(1 <= P_{j} <= 20\)

For 100 Points: Original constraints.

 

 

SAMPLE INPUT
6
2 2 1
1 3
3 3 1 1
2 3 2
3 3 1 1
3 2 3 2
SAMPLE OUTPUT
3
Explanation

There are 6 numbers.

1st number = 2 x 1 = 2;

2nd number = 3

3rd number = 3 x 1 x 1 = 3

4th number = 3 x 2 = 6

5th number = 3 x 1 x 1 = 3

6th number = 2 x 3 x 2 = 12

So, you can choose {1st, 2nd, 3rd, 6th} and {1st, 2nd, 5th, 6th} and {1st, 3rd, 5th, 6th}. These are the 3 ways. 

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 512 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?