That is not true imo, every positive integer has a factor 1, and the reciprocal of 1 is 1 only and that will give us the minimum sum of reciprocals to be 1 atleast. Also A/B is equal to S/N, so A will always be greater than or equal to B.
@admin
The test cases for this problem are very weak .Please donot consider this problem for rank/ rating calulation or fix the weak test cases and then revaluate the problem for everyone.
There are more than 3000 submissions this problem . Many got AC without checking that sum of divisors ==x .
EX -for X=5, A=5, B=3 ,but it should be -1 but many people’s code will give 3 .
The legacy of CodeChef will be destroyed by increasing number of people becoming 4* coders. Please restore the legacy by rejudging this problem.
Why were no impossible scenarios covered? I spent 20 mins solving it for the borderline cases where we get the value of N but the sum of reciprocal of its divisors is not A/B. My rank went from 150 to 800 just because I solved it for the difficult version. How can you give something so easy at this point in a contest? How was this deserving to be at the 4th position? The discrepancy between the 4th and 5th questions is alarming. You guys can do better than this man. If I can think of good test cases, why cant you?
@rishabhdevil I think this editorial required Little Improvement to make people understand how to come up with this solution.
Mathematical Approach
Let f(n) be the sum of reciprocals of all the divisors of n :
f(n) = \sum_{d|n}^{}1/d = \frac{A}{B}
Multiplying n on both sides.
n \cdot f(n) = \sum_{d|n}^{}n/d
Since, every divisor comes in pair n / d is also a divisor therefore it can be altered into d in above equation.
=> n \cdot f(n) = \sum_{d|n}^{}d
=> n \cdot f(n) = X
=> n = X \cdot\frac{1}{f(n)}
=> n = X . \frac{B}{A}
Intuition
We know that : \frac{1}{a} + \frac{1}{b} + \frac{1}{c} … = \frac{cm/a + cm/b+cm/c + ...}{cm}
Here cf means common multiple
Similarly Common Multiple for all divisors of n will be n itself. Therefore,
f(n) = \frac{A}{B} = \frac{n/d_1 + n/d_2 + n/d_3 + ...}{n}
And as we know n / d is another divisor. Therefore,
=> f(n) = \frac{d_1 + d_2 + d_3 + ...}{n}
=> f(n) = \frac{X}{n}
=> n = \frac{X}{f(n)}
=> n = \frac{X . B}{A}
Can we get all the test cases? I used the X*B/A method and checked sum of factors. However, I still have WA.
My code: CodeChef: Practical coding for everyone