I encountered this
1673. Admission to Exam @ Timus Online Judge
problem some time ago…i know it can be done by use of euler totient.
Can somebody explain how to solve it?
Did you get explanation? I am facing same problem as like you
//untested
I’m going to assume that you know the answer is basically the smallest n such that \phi(n) = k. Let \phi^{-1}(x) denote smallest y such that \phi(y) = x.
Let p be the set of all primes that divide n . Let \prod p_{i}^{e_i} = n. It is well known that \phi(n) = \prod p_{i}^{e_i - 1}(p_{i} - 1) = k. Let us now consider the possible cases. If k+1 is prime, the smallest answer is k+1. If k+1 is not prime, we can deduce that it either has no solution, or there are at least 2 primes in p. That means at least one of p_1 - 1 or p_2 - 1 is \le \sqrt{k}. We can find them by iterating over all x-1 where x is prime and x-1\le \sqrt{k}. Let us say we have found some x. We can deduce
\phi^{-1}(k) = \min_{(x-1)x^{y-1} | k}\Bigg(x^y\times \phi^{-1}\bigg(\frac{k}{(x-1)x^{y-1}}\bigg)\Bigg)
Using this, we can obtain a O(\sigma_0(k)\pi(\sqrt{k})\log(k) + \sqrt{k}\log k + \sigma_0(k)\sqrt{k}) solution.
Okay we need one more optimisation. We must also pass the set of x \le \sqrt{k} such that x-1 divides k. If something doesn’t work after the division, we can ignore it. This will optimise to
O(\sigma_0(k)\log^2{k} + \sqrt{k}\log k + \sigma_0(k)\sqrt{k})
Still I can only upper bound to 10^8 modulo operations in the worst case. So you might need a more optimised approach to check if k+1 is prime.
2 Likes