Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

Блог пользователя ahmed_drawy

Help with atcoder problem since the editorial is in JAPANESE
Автор ahmed_drawy, история, 6 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить