Дано число 
, затем 
натуральных чисел. Найдите количество пар элементов, где оба элемента будут являться различными числами, при этом оба числа являются полными квадратами.
Входные данные
В первой строке подается натуральное число 
. В каждой строке после записано одно натуральное число, не превышающее 
.
Переборное решение:
f = open("10_A.txt")
n = int(f.readline())
a = []
for i in range(n):
a.append(int(f.readline()))
cnt = 0
for i in range(n):
for j in range(i + 1, n):
if a[i] != a[j] and a[i] ** 0.5 == int(a[i] ** 0.5) and a[j] ** 0.5 == int(a[j] ** 0.5):
cnt += 1
print(cnt)
Эффективное решение:
f = open(’10_B.txt’)
n = int(f.readline())
# Список количеств чисел, где индекс равен корню из числа
# Например, под индексом 7 хранится количество чисел 49
nums = [0] * 101
count = 0 # Общее количество чисел-квадратов
ans = 0
for i in range(n):
x = int(f.readline())
# Проверяем, является ли текущее число полным квадратом
if x ** 0.5 == int(x ** 0.5):
# Так как числа должны быть разными, x составляет пары со всеми
# встреченными до этого полными квадратами, кроме равных себе чисел
ans += count - nums[int(x ** 0.5)]
# Увеличиваем количество встреченных чисел x
nums[int(x ** 0.5)] += 1
# Увеличиваем общее количество квадратов
count += 1
print(ans)