問題はこれ
E - Max GCD
解説
操作前を とし、操作が終わったものを とする。
最終的に、全て の倍数になったとすると、
は全て で割り切れる。
つまり、 も で割り切れる。
和は操作で不変なので、
も で割り切れる。
つまり、解の候補は の約数に限られる。
ここで、 でそれ以外は とすることで、全ての約数で割り切れる をつくれることが分かる。
しかし、操作回数の制限 があるため、解はより複雑なものになる。
ここで、 の約数 を一つ固定する。
の倍数を考えるの、 で考えれば良い。
を を昇順に並べたものとする。
のうち、いくつかを して、残りを できるとき、
の倍数になる数列を 回で実現できる。
これは、小さい方から取ったほうがより小さくできる。
を小さい方から大きい方に足していくつもりで操作すれば最適になる。
理解の助けになるかもしれないので、いくつか Remark を述べる。
- 各 に対して、 は、 か かのいずれか一方の操作が行われる。ただし、 倍の差はある。
- となるとき、その操作を実現できる。
- 上の主張と「小さい方から使えば良い」を使うと、ある地点より左は全て の操作が行われて、残りの右の部分は全て の操作が行われたものが、 を実現する。
解答
解答
def factors(N): #約数を全て求める。ただし、順不同 from collections import deque ret = deque() middle = int( N**(1/2)) for i in range(1, middle): if N%i == 0: ret.append(i) ret.append(N//i) if N%middle == 0: ret.append(middle) if middle != N//middle: ret.append(N//middle) return ret def main(): N, K = map( int, input().split()) A = list( map( int, input().split())) sa = sum(A) R = factors(sa) l = len(R) E = [0]*l ans = 0 for r in R: cnt = 0 E = list( map( lambda x:x%r, A)) E.sort() s = sum(E) now = 0 if s - E[-1] <= K: if ans < r: ans = r continue if s == 0: continue v = 0 w = N-1 cnt = 0 while w-v != 0: if E[v] == 0: v += 1 continue if E[w] == 0: w -= 1 continue if E[v] + E[w] >= r: E[v] -= r - E[w] cnt += r - E[w] E[w] = 0 w -= 1 else: E[w] += E[v] cnt += E[v] E[v] = 0 v += 1 if cnt <= K: if r > ans: ans = r print(ans) if __name__ == '__main__': main()
おまけ
計算量は、約数列挙が で、
各操作は並べ替えが律速段階になって、 で、
あわせて、
となる。