Дано число n – количество чисел. В следующей строке дано n чисел, каждое не больше 1000.
Вам необходимо вывести количество таких пар чисел (a, b), что НОК (a, b) = НОД (a, b).
НОК (a, b) - наименьшее общее кратное этих двух чисел, то есть наименьшее число, которое делится сразу на оба числа.
\( НОК (20, 30) = 60\).
НОД (a, b) – наибольший общий делитель этих двух чисел, то есть наибольшее число, на которое делятся оба числа.
\(НОД (20, 30) = 10\).
Напишите эффективную по памяти и времени программу.
Входные данные
В первой строке вводится натуральное число
n – количество данных вам чисел.
Во второй строке вводятся сами числа, каждое из них целое и принадлежит отрезку
[0; 1000].