A/B Матрица

Revision ru2, by nechaev, 2021-02-03 19:10:49

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

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

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

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

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

$$$ n a = m b, $$$

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

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

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

То есть в качестве $$$d$$$ мы всегда можем выбрать $$$a$$$.

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 Первая редакция (сохранено в черновиках)