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

Автор Watermelon, история, 3 года назад, По-английски

Hi, I was reading the editorial of the Half Sequence problem from recent cookoff. One of the statements has been left for readers to prove and I am unable to prove it. The statement is as follows.

"Observe that any single number less then 1e9 can be made up of atmost 9 distinct prime numbers. This means that if GCD([B[0], B[1], ..., B[N]) = 1, where N >= 9 then there must exist atleast one subset of length at most 9 whose elements have GCD=1. (Proof left as an exercise)"

I have trouble understanding the last line. Why must there exist that subset?

Полный текст и комментарии »

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

Автор Watermelon, история, 3 года назад, По-английски

I am solving this problem and I am unable to solve it. I read the editorial but don't understand it. I feel sad to not even understand the editorial of a 1400 rated problem. https://codeforces.com/problemset/problem/388/A

Can someone please explain this to me? Thanks.

Полный текст и комментарии »

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