Вчера решил задачу 1360G - A/B Matrix следующим образом 106287665. Хоть мое решение и компактно в реализации, его суть не очевидна и выйти на него было не просто.

Посмотрел в Editorial в надежде, что авторское решение будет проще. Stepavly предлагает подобрать смещение $$$d$$$ такое, что бы выполнялось отношение

Давайте разберемся почему вообще оно должно работать.

Первый важный факт, на который мы будем опираться, установлен равенством

смысл которого обьясняется в эдиториале.

Из него мы сразу же можем заметить, что

То есть, в качестве $$$d$$$ мы всегда можем выбрать $$$a$$$ и заполнить матрицу подобно тому, как это указано на картинке снизу

Какоово же количество ячеек, заполненых единицами, или, альтернативно, суммарная площадь покрытая разноцветными прямоугольниками? Она равняется $$$n \cdot a$$$. И тут нам пригождается наше уравнение $$$n \cdot a = m \cdot b$$$ потому, что получается, что всеми этими единицами можно заполнить прямоугольник высотой $$$b$$$ и шириной $$$m$$$ как указано на следующей картинке.