perogram

No.982 Add

Quiz

https://yukicoder.me/problems/no/982

公式解法

https://yukicoder.me/problems/no/982/editorial

考えたこと

  • gcd=1じゃなければ-1
  • lcmの部分まで考えれば良さそう
  • 実際にそれで求まるのだが、公式解説や他の人の解説では分からなかった
  • それは私の数学力による

具体例を表で眺める

f:id:peroon:20200219024148p:plain

  • A=21, B=16で表を描く。ここで肌色の箇所の数字は作ることができる(いい整数)
  • lcm = 21x16 = 336
  • lcmより大きい値は全て作れそう。ということで337を検索してみると存在する。(列64+行273)
  • gcd=1なので、乗数が負を許せば1刻みで作れる気はする
    • -1 = 21x3 + 16x(-4)
    • 1 = 21x(-3) + 16x4
  • lcmを超えた領域では、乗数が負にならないことを保ちながら1刻みで作れるのだろう
  • ふわっとした理解だが、ここまでとする