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