Given a number n – amount of numbers. The next line contains n numbers, each not greater than 1000.
You need to output the number of pairs of numbers (a, b) such that LCD (a, b) = gcd (a, b).
LCM (a, b) is the least common multiple of these two numbers, that is, the smallest number that is divisible by both numbers at once.
\( LCM (20 , 30) = 60\).
GCD (a, b) – the greatest common divisor of these two numbers, that is, the largest number that both numbers are divisible by.
\(gcd (20, 30) = 10\).
Write a memory and time efficient program.
Input
The first line contains a natural number
n – the number of numbers given to you.
The second line contains the numbers themselves, each of them is an integer and belongs to the segment
[0; 1000].