Perfect Cubes

3.6

18 votes
Hash Maps, Math, Medium, Meet In the Middle, Number Theory, Primality test, Prime Factorization
Problem

You have N numbers, X1,X2,X3,...,XN. 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 Xa,Xb,Xc,Xd is a perfect cube.

A number Z is said to be a perfect cube if there exists an integer Y such that Z=Y3.

Since the numbers can be quite large, so instead of giving a number directly, you will be given Ki  integers, P1,P2,P3,...,PK. Formally, each number Xi  is a product of P1,P2,P3,...,PK.

Input Format

First line will contain N
Each of next N lines will start with Ki. Next Ki integers P1,P2,P3,...,PK  will be sperated by a space.

4<=N<=1000

1<=Ki<=100

1<=Pj<=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<=501<=Ki<=251<=Pj<=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
Time Limit: 2
Memory Limit: 512
Source Limit:
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. 

Editor Image

?