Problem Statement is here. I searched for the editorials. But did not get a good one. It was recommended by many people in Quora. Can anyone please help in this question?
First of all you should be able to come up with a formula for phi(m) in terms of m and its prime factors. This can be easily searched online (here) or derived using inclusion exclusion formula. Now, in the formula you can notice that m occurs, which in the problem NDIVPHI simply cancels with the numerator. Now the remaining terms are simply the distinct prime factors of m arranged in some manner. Since, the question asks for finding the smallest possible value of integer, there is no point in having the same prime again as a divisor of m. So we take distinct prime factors only. Finally we want to maximise the value of the function so we simply go on taking primes till the number formed is less than m.
Here is a final implementation in python, (easy to handle large numbers) of the above described process.
If you feel your question was answered, mark it as accepted.
1 Like
“Since, the question asks for finding the smallest possible value of integer, there is no point in having the same prime again as a divisor of m. So we take distinct prime factors only. Finally we want to maximise the value of the function so we simply go on taking primes till the number formed is less than m.” ---- I have doubt here … the {m / phi(m)} is finally reduced to [p1 * p2 * p3 * …] / [(p1 - 1)(p2 - 1)(p3 - 1)…] where p1 , p2 ,p3 … are distinct prime factors of m. But the input N can be large as 10^40 so m can also be very large and how do we compute the prime factors for such large m in C++ . Please tell some possible method for its C++ implementation @likecs or anyone else. Thanks in advance 
@jaydeep, we do not have to find the prime factors of the number, instead find the number itself. I suggest you to read the question again Also, c++ solution exist but you would need to write your big integer library for it or else copy someone else 