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

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

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

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

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

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

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

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

Почему же наше заполнение обязательно является однородным? Доказать то, что высота каждой колонки является одинаковой можно по индукции: Пусть после добавления $$$l$$$ кирпичиков у нас имеется какое-то количество полностью заполненых строк $$$\left\lfloor\frac{l \cdot a}{m}\right\rfloor$$$ и последняя строка, в левой части которой находится какое-то количество $$$l \cdot a \bmod m$$$ заполненых ячеек. На следующей итерации мы добавляем кирпичик точно в конец незаполненой строки, потому, что его начало отстоит ровно на $$$a$$$ позиций от начала предыдущего кирпичика, а следовательно интересующее нас свойство снова сохраняется. Ну и разумеется если $$$l=n$$$, мы имеем $$$n \cdot a \bmod m = 0$$$. То есть в каждой колонке действительно будет ровно $$$b$$$ единиц.