Олимпиадный тренинг

Задача . Я. Свиридов


Задача

Темы:
Дано число 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) Свиридов Ярослав

time 500 ms
memory 32 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя