問題はこちら
問題概要
長さの数列が与えられる.この数列の要素を一つ選びを加えるという操作を回まで行うことができるとき,の全要素のgcdの最大値を求めよ.解説
となるための最小操作回数が以下であるかが分かればいい(そのようなで最大のものが答え).最大のものさえ見つけられればいいので「」を「」としてもいい.のとき,であるのでよりが答え.ただしでないならの範囲に答えはない.
のとき,が同じ値であるの数を計算すればいい.であるのはの範囲にあるものである.これは累積和を用いれば1つの範囲につきで求められる.
であるので全体でとなる.