No.982 Add

Quiz

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

公式解法

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

考えたこと

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

具体例を表で眺める

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

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～