deepkamal's blog

Very Nice Number theory Problem
By deepkamal, history, 3 years ago, In English

I was trying to solve this number theory problem from 2012-2013 ACM-ICPC, NEERC, Западный четвертьфинал. 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.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 3   Vote: I like it +11 Vote: I do not like it
Hint 1
Hint 2
Hint 3
→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 .

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply