perogram

D. Fun with Integers 図示

Quiz

https://codeforces.com/contest/1062/problem/D

観察

  • サンプル1より、a=2からスタートしたときはジャンプを繰り返して戻ってこれる。図示すると、

f:id:peroon:20200206114437p:plain

  • aとbが整数倍関係(0倍、1倍は不可。範囲内にあること)にあるとき、このループが作れる
  • ループの途中で他のループを組み込むことができる
  • よって、全ての整数倍関係(a, b)についてのループが合体できる
  • 考えうる組(a, b)で得られる得点の総和が答えとなる

(7, 21)とかも組み込める?

  • Yes
  • (7, 21)はつながっている
  • (7, 14)はつながっている(7と21の間にある7の倍数かつ偶数)
  • (2, 14)はつながっている
  • 図示すると、下記のように、独立したループが存在しないことが確認できる

f:id:peroon:20200206115359p:plain