Vasiljko's blog

Maybe phi(n)
By Vasiljko, history, 7 years ago, In English

Given N. We can make equality with K numbers (can be repeated) like this:

(a1+1)*(a2+1)*...(aK+1) = N*a1*a2*...*aK

Find the smallest possible value of K for which there are integers that satisfy above equality

Sample 1: Input:4 --> Output:2 --> Explanation: Integers a1 = 1 and a2 = 1 are satisfying equation.

2 < n < 1000 TL: 0.1s ML: 64MB

I thought that the answer is phi(n), but that's just a guess.

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

»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Are you sure the answer is phi(n) because for n = 5, according to you the solution is 4, but i get a better solution as 3.

(1 + 1) * (1 + 1) * (4 + 1) = 5 * 1 * 1 * 4.

Although, I am still not able to come up with full solution, I would like to know what the source of the problem is?

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

    Thank you for the test, I couldn't find solution for n=5 so phi(n) was just a guess. Problem is from competition that is held in faculty of mathematics in Serbia. Competition is matf++ 2016, but you need to translate page.

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Try dynamic programming. dp[n] will be the answer for the original problem. To calculate it:

The idea is to try every divisor of n to start the left sequence. Now you have to solve a smaller problem where you'll want to find the same sequence for:

EDIT: this solution is incorrect, as pointed out by ABalobanov. Since you don't depend only on previous states you cannot build this dp direclty. You have to do something like ivan100sic proposed.

→ Reply
»
7 years ago, # |
  Vote: I like it +9 Vote: I do not like it

This is the actual source of the problem (Task A3):

http://www.math.bas.bg/keleved/shumen2010

My solution
→ Reply