All Tracks Data Structures Hash Tables Basics of Hash Tables Problem

Similar Chocolates
/

Data Structures, Hash Maps, Hash Tables, Implementation

Problem
Editorial
Analytics

There are $$N$$ chocolates denoted by array $$A$$ where $$A[i]$$ is the length of the $$i$$-th chocolate. Alice can melt each chocolate and then convert it into a chocolate whose length is any divisor of the number $$A[i]$$. So, a chocolate of length $$A[i]$$ can be converted into $$X$$ different types of chocolate where $$X$$ is the count of divisors of the number $$A[i]$$. So you need to count the total unordered pair of chocolates such that their $$X$$ value is same.

Input Format
The first line contains an integer $$N$$ as input denoting the total number of elements in the array $$A$$.
The next line contains $$N$$ space-separated integers that denote the elements of the array $$A$$.

Output Format
In the output, print the total number of ways as mentioned in the statement.

Constraints
$$1 \le N \le 10^5$$
$$1 \le A[i] \le 10^6$$

SAMPLE INPUT
3
2 3 4
SAMPLE OUTPUT
1
Explanation

There is only one possible value i.e. to pick the chocolates $$2$$ and $$3$$ as both of them have $$2$$ divisors hence their $$X$$ value is same.

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

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?