E: Понятно, что две противоположные вершины квадрата лежат на одной даигонали. Давайте зафиксируем диагональ. Каждой клетке на ней поставим в соответсвие четыре числа L, R, U, D (на сколько можно уйти в каждом направлении, прежде чем встретиться нолик). Рассмотрим клетки в порядке возрастания номера строки. Пусть сейчас мы стоим в строке i. Строкаr < i подходит, если выполняется условие типа r + min(D(r), R(r)) >= i and i - min(U(i), L(i)) >= r. Это похоже на какие-то двумерные запросы. На самом деле, r + min(D(r), R(r)) от i никак не зависит. Поэтому r можно просто вовремя выкидывать, когда i становаться слишком большим. Теперь все свелось к количеству чисел на отрезке [i - min(U(i), L(i)), i]. Ну а это уже просто запросы к фенвику. Возможно, код внесет больше ясности.

C: Есть весьма простое решение за O(N * N + N * Q). Зафиксируем левую границу отрезка. Будем идти вправо и запоминать текущий gcd. Дойдя до конца при фиксированном l, пройдемся по запросам и прибавим соответсвующую префиксную сумму тем, у которых левая граница левее или совпадает с l. Все. Вроде понятно, почему это правильно. Если аккуратно написать, то это уже заходит.

Бонус: можно развить эту идею дальше и получить решение за
O(N * log MAX_A * log N + Q * log N). Какие наблюдения нам потребуются?

1. Для фиксированного l и всех возможных r, есть не более O(log MAX_A) разных значений gcd и r-ки с одинаковыми значениями образуют непрерывный отрезок. Моменты перехода можно находить за O(log N) каждый спуском по дереву отрезков.

2. А теперь давайте перебирать l справа налево, находя подотрезки с одинаковым gcd и добавляя константу на них.

3. Утверждение: когда l становиться равным левой границе какого-то запроса, ответ на него-просто сумма на нем.

Нам нужны операции: следующий другой gcd, прибавление константы на интревале и сумма на отрезке. Понятно, что дерево отрезков это все делать умеет. Возможно, решение звучит немного страшно, но код получается сравнительно простой.