Вчера решил задачу 1360G - A/B Matrix следующим образом 106287665. Хоть мое решение и компактно в реализации, его суть не очевидна и выйти на него было не просто.
Посмотрел в Editorial в надежде, что авторское решение будет проще. Stepavly предлагает подобрать смещение $$$d$$$ такое, что бы выполнялось отношение
Давайте разберемся почему вообще оно должно работать.
Первый важный факт, на который мы будем опираться, установлен равенством
смысл которого обьясняется в эдиториале.
Из него мы сразу же можем заметить, что
То есть, в качестве $$$d$$$ мы всегда можем выбрать $$$a$$$ и заполнить матрицу подобно тому, как это указано на картинке снизу
Какоово же количество ячеек, заполненых единицами, или, альтернативно, суммарная площадь покрытая разноцветными прямоугольниками? Она равняется $$$n \cdot a$$$. И тут нам пригождается наше уравнение $$$n \cdot a = m \cdot b$$$ потому, что получается, что всеми этими единицами можно заполнить прямоугольник высотой $$$b$$$ и шириной $$$m$$$ как указано на следующей картинке.