Maybe phi(n)

Revision en3, by Vasiljko, 2017-10-03 22:58:59

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Vasiljko 2017-10-05 09:31:05 1 Tiny change: 'e equality.\n\n\nSamp' -> 'e equality\n\n\nSamp'
en3 English Vasiljko 2017-10-03 22:58:59 11 Tiny change: 'n Input:4\n Output:2\n Explan' -> 'n Input:4 --> \n Output:2 -->\n Explan'
en2 English Vasiljko 2017-10-03 22:58:34 38
en1 English Vasiljko 2017-10-03 22:58:07 484 Initial revision (published)