Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Бобры-Зомби

(Время: 3 сек. Память: 16 Мб Сложность: 56%)

Вы сидите на вершине дерева с небольшой командой выживших в центре бобро-зомби апокалипсиса. На земле вас окружили N бобров-зомби, которые вот-вот сточат ствол дерева! У каждого бобра-зомби есть свой размер Si, выраженный натуральным числом.

Учёный, который недавно погиб от несчастного случая, рассказал, что, если стравить двух бобров-зомби между собой с помощью особых радиоволн, то они образуют могущественного Бобротрона, размер которого будет равен произведению размеров стравленных бобров. Последними словами учёного было уточнение, что если размер Бобротрона будет квадратом целого числа, то он будет на вашей стороне, вселит ужас в остальных бобров-зомби и заставит их убежать!

Срочно посчитайте, сколькими способами можно создать доброго Бобротрона, стравливая двух бобров-зомби!

Входные данные

Первая строка входного файла INPUT.TXT содержит целое число N – количество бобров-зомби (2 ≤ N ≤ 200 000).

Вторая строка содержит N целых чисел Si, разделённых пробелами – размеры бобров-зомби (1 ≤ Si ≤ 200 000).

Выходные данные

В выходной файл OUTPUT.TXT выведите целое число – количество пар бобров, которые смогут образовать доброго Бобротрона.

Примеры

INPUT.TXTOUTPUT.TXT
14
1 4 9 16
6
24
2 4 6 8
1

Примечание

В первом примере подойдёт любая пара бобров.

Во втором примере подойдёт лишь пара бобров с размерами 2 и 8.


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2021 / 2022
 2022 / 2023
 A. Ближайшее нечётное
 B. Бобры-Зомби
 C. CSV Reader
 D. Суперпозиция
 E. Системы счисления
 F. Раздел империи
 G. Крыша
 H. Хардкорный массив
 I. Виталя и Рома
 J. Квадратов много не бывает

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ИНН 246305493507, E-mail: admin@acmp.ru