ahmed_drawy's blog

Help with atcoder problem since the editorial is in JAPANESE
By ahmed_drawy, history, 6 years ago, In English

i want help in atcoder beginner contest 112 problem D since the editorial is in japanese and i didn't find any related topic on google

i don't know how to find the MAX GCD for a sequence of numbers of length N (not ordered any sequence of length N) and sum of sequence = M

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Let's say the answer is x, then every ai can be written as x * bi where bi ≥ 1

x * b1 + x * b2 + ... + x * bn = m

x(b1 + b2 + ... + bn) = m

therefore m should be divisible by x. So you can try all divisors of m.

Since bi ≥ 1, then sum of all bi's should be at least n, i.e.

From all the divisors that satisfy the previous rule, find the maximum one.

→ Reply