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

Very Nice Number theory Problem
Автор deepkamal, история, 3 года назад, По-английски

I was trying to solve this number theory problem from 2012-2013 ACM-ICPC, NEERC, Western Subregional Contest. The problem name is L : sum. In this problem we given a number N and we want K(any K that works) natural numbers such that their sum is N and sum of their reciprocal is 1. How to solve this ? I tried various approaches but wasn't able to generalize for all N.

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

»
3 года назад, # |
← Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится
Hint 1
Hint 2
Hint 3
→ Ответить
  • »
    »
    3 года назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Hi, I got the idea that how we can do 2 * N + 2 from N, or 2 * N + 9 from N, but how we do for some even number say N for whom solution might exist but not for (N-2)/2 .

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
      ← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

      Let's assume answer always exists starting with $$$X$$$.

      It means answer exists for all numbers from $$$X$$$ to $$$2X+10$$$.

      If we will infinitely reduce $$$N \ge X$$$ to $$$(N-2)/2$$$ or $$$(N-9)/2$$$, in one moment $$$N$$$ will be in $$$[X; 2X+10]$$$ range. It is easy to see it is impossible to skip this range ($$$(2X+11-9)/2 \ge X+1$$$)

      And In practice $$$X$$$ is not that big, so we can find all answers for numbers from $$$1$$$ to $$$2X+10$$$ using some bruteforce.

      → Ответить