A/B Матрица

Revision ru3, by nechaev, 2021-02-03 19:25:34

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

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

$$$ n \cdot d \equiv 0 \mod{m} $$$

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

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

$$$ n \cdot a = m \cdot b, $$$

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

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

$$$ n \cdot a \equiv 0 \mod{m}, $$$

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

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru6 Russian nechaev 2021-02-03 20:57:48 0 (опубликовано)
ru5 Russian nechaev 2021-02-03 19:45:23 1 Мелкая правка: 'g)\n\nКакоово же кол' -> 'g)\n\nКаково же кол'
ru4 Russian nechaev 2021-02-03 19:43:31 784 компактное заполнение
ru3 Russian nechaev 2021-02-03 19:25:34 555 Мелкая правка: 'e.png)\n\n' -> 'e.png)\n\n![ ](https://mirror.codeforces.com/10c412/bricks-2.png)'
ru2 Russian nechaev 2021-02-03 19:10:49 85 bricks 1
ru1 Russian nechaev 2021-02-03 16:03:18 760 Первая редакция (сохранено в черновиках)