Сколько существует пар натуральных чисел , удовлетворяющих условиям не кратно 8 таких, что не является квадратом целого числа?

Рассмотрим все натуральные пары (z, n) с z ≤ 1000 и n ≤ 10000, где z не кратно 8. Всего натуральных чисел z от 1 до 1000 – 1000 штук. Из них те, что кратны 8, их количество равно ⌊1000/8⌋ = 125. Значит, допустимых z 1000 – 125 = 875. При n от 1 до 10000 получаем общее число пар

  875 · 10000 = 8 750 000.

Наша задача – посчитать, сколько среди этих пар удовлетворяют условию, что выражение z^n + z + 1 не является квадратом целого числа. Для этого найдем те пары, для которых выражение оказывается квадратом, и вычтем их из общего числа.

Заметим, что для n...