Как найти число смежных подпоследовательностей / подмассивов, произведение которых можно выразить как разность квадратов 2 случайных целых чисел?

Question

Итак, давайте предположим, что данная последовательность {2,1,3,4}. Смежные подпоследовательности, которые удовлетворяют условию вопроса, будут {1}, {3}, {4}, {1,3}, {1,3,4}, {3,4}, {2,1,3 , 4}. Поэтому общее число смежных подпоследовательностей / подмассивов равно 7.

Мой подход: я немного подсчитал и обнаружил, что все числа, которые являются нечетными, или числа, которые делятся на 4, будут удовлетворять условию вопроса. Но когда я пытаюсь написать программу, она берет O (n ² ) в худшем случае, поскольку я проверяю каждую смежную подпоследовательность / подмассив. Можете ли вы помочь мне найти оптимальный подход?

Answer 1

Любое число может быть представлено как разность квадратов, если оно нечетное, или кратное 4. Проблема возникает, когда у продукта есть только один 2 в простой факторизации. Таким образом, мы можем пометить их. (т.е. все 2) Учитывая это, мы можем легко сделать вывод, что только то, что не является допустимым подмассивом для данного условия, является

[odd, 2, odd, 4*n, odd]
[0,   1,   2,    3,   4]

. Мы можем видеть, что позиция 3 не будет ни в одном из действительных подмассивов, поэтому Вы можете рассчитывать шансы слева и справа. Число подмассивов, в которых позиция 1 принимает участие, недопустимые подмассивы: [нечетные, 2], [2, нечетные], [2], [нечетные, 2, нечетные]

Вычитание 15 - 4, отсюда и ответ равно 11.

Делайте это для каждого числа, у которого есть две одинарные в своей первичной факторизации.

Answer 2

число может быть выражено только как разность двух квадратов, только если оно нечетное или делится на 4.

int main()
{

    long long int t, n, i, j, a[100000];

    cin >> t;

    while (t--)
    {

        int c = 0, d = 0;

        long long int sum = 1;

        cin >> n;

        for (i = 0; i < n; i++)
            cin >> a[i];

        for (i = 0; i < n; i++)
        {

            if (a[i] % 2 != 0 || a[i] % 4 == 0)

                d++;
            sum = a[i];
            for (j = i + 1; j < n; j++)
            {

                sum = sum * a[j];

                cout << sum << endl;

                if (sum % 2 != 0 || sum % 4 == 0)

                    c++;
            }

            sum = 1;
        }

        cout << c + d << endl;
    }

    return 0;
}