Задача

Дорогие ребята!
Наблюдая за тем, как Шарик распиливал нестандартную шахматную доску, я также решил задать для вас задачку: “А сколько разных квадратных и прямоугольных (не считая квадратных) досок мог бы получить при распиливании Шарик из найденной им нестандартной прямоугольной шахматной доски размером $M\times N$?”

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

В первой строке количество заданий Печкина $K$, в последующих $K$ строках по два целых числа $M$ и $N$ $(1 \leqslant K, M, N \leqslant 100)$, разделённых пробелом.

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

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

Тесты

№	Входные данные	Выходные данные
1.	1 3 2	8 10
2.	2 4 4 2 2	30 70 5 4
3.	4 3 3 25 46 100 100 1 1	14 22 12350 338975 338350 25164150 1 0

Код программы

#include <iostream>
using namespace std;

int main() {
    int k; // Количество заданий
    cin >> k;
    for(int l = 0; l < k; l++)
    {
        int m, n; // Размер шахматной доски
        cin >> m >> n;
        int res = 0; // Количество кусков, на которые мы можем разделить доску
        for(int i = min(m, n); i >= 0; i--) // Находим количество квадратов
        {
            res += (m - i) * (n - i);
        }
        cout << res; // Вывод количества квадратных досок
        res = res * - 1; // Чтобы не учитывать квадратные доски, сразу вычитаем их
        for(int i = m - 1; i >= 0; i--) // Находим количество прямоугольников
        {
            for(int j = n - 1; j >= 0; j--) 
            {
                res += (m - i) * (n - j);
            }
        }
        cout << ' ' << res << endl; // Вывод количества прямоугольников
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int k; // Количество заданий

cin >> k;

for(int l = 0; l < k; l++)

{

int m, n; // Размер шахматной доски

cin >> m >> n;

int res = 0; // Количество кусков, на которые мы можем разделить доску

for(int i = min(m, n); i >= 0; i--) // Находим количество квадратов

{

res += (m - i) * (n - i);

}

cout << res; // Вывод количества квадратных досок

res = res * - 1; // Чтобы не учитывать квадратные доски, сразу вычитаем их

for(int i = m - 1; i >= 0; i--) // Находим количество прямоугольников

{

for(int j = n - 1; j >= 0; j--)

{

res += (m - i) * (n - j);

}

cout << ' ' << res << endl; // Вывод количества прямоугольников

}

return 0;

}

Объяснение

Ответом на каждый запрос будет количество квадратов и прямоугольников которые можно получить из нашей шахматной доски размера $M\times N$. Для вычисления количества квадратов нам надо посчитать, сколько квадратов каждого возможного размера поместится в нашей шахматной доске. Аналогично для прямоугольников. Пример с доской $3\times 2$ разобран на картинке.

Пояснение к первому тесту

Для подсчёта квадратов, нам следует отдельно считать их количество для каждого возможного размера. Таким образом сначала идут квадраты $1\times 1$, то есть $M\cdot N$ квадратов. Далее, квадратов $2\times 2$ помещаются ровно на $1$ меньше горизонтально и на $1$ меньше вертикально, значит получаем $(M-1)\times (N-1)$. Соответственно, $(M — 2)\times (N — 2)$ для квадратов $3\times 3$. И так продолжаем пока квадрат помещается в нашу доску.

Аналогично мы поступаем и с прямоугольниками. Однако считая количество прямоугольников каждого размера, нам нужно считать сколько поместится прямоугольников размера $(1\times 1), (1\times 2)\dots (1\times N)$. Также $(2\times 1), (2\times 2)\dots (2\times N)$. И так до $(M\times 1), (M\times 2)\dots (M\times N)$. Это довольно просто реализовать используя вложенный цикл.

Не стоит забывать, что квадрат — тот же прямоугольник, но с равными сторонами и в нашем цикле мы считаем все прямоугольники. А так как квадраты мы не должны учитывать, то после нахождения числа прямоугольников, нам нужно вычесть из него количество квадратов. В коде после нахождения и вывода числа квадратов, мы домножили это число на $(-1)$ и и уже после прибавили к нему количество прямоугольников, таким образом не учитывая квадраты.