D. Fun with Integers 図示

Quiz

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

観察

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

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

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

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

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