kanpurin https://blog.hatena.ne.jp/kanpurin/ かんプリンの学習記録 https://kanpurin.hatenablog.com/ ABC 解説 競技プログラミング 数論 問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列が与えられる．この数列の要素を一つ選びを加えるという操作を回まで行うことができるとき，の全要素のgcdの最大値を求めよ．解説となるための最小操作回数が以下であるかが分かればいい(そのようなで最大のものが答え)．最大のものさえ見つけられればいいので「」を「」としてもいい．であるから，各についてとなるための最小操作回数が分かればいい．これはであるのでが操作回数となる．これをすべてのについて求めればいいが，の取り得る範囲が大きいので間に合わない．のとき，であるのでよりが答え．ただしでないならの範囲に答えはない．のとき，が同じ値であ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkanpurin.hatenablog.com%2Fentry%2F2021%2F09%2F20%2F210151" title="ARC126 C - Maximize GCD - かんプリンの学習記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2021-09-20 21:01:51 rich https://kanpurin.hatenablog.com/entry/2021/09/20/210151 1.0 100%