DIVREC Editorial

This is due to the limits, being very large.
A,B,X<=1e9

Let’s consider, this cases X =1e9, A=1 and B=1.
So, if we calculate n it will be X*B/A = 1e9.

Then if we run, the function to calculate the sum of divisors of 1e9. It will take very long time.

Instead we can add one more condition to sum of divisors function, if at any point,
sum of divisors > X, print -1.

My solution.

I did this question in O(1) time complexity and O(1) space complexity. Do checkout.
My Solution

1 Like

I don’t think it was intuitive to come up to the logic of making x = min ( x , sum of divisors up to the sqrt(n)).

Here is the proof : Number of divisors / sum of divisors

1 Like

Same logic bro :slight_smile:

my solution

Can someone please check why it is giving TLE. I did exactly the same as written in the editorial

Yes , some of the codes are giving 3 for X=5, A=5, B=3 ,but it should be -1. Test case are Weak @admin

1 Like

You got lucky with the weak test cases, your code wouldn’t work. For example x = 3, a = 3, b = 1

Your code is not 100% correct ,

for X=5, A=5, B=3 ,but it should be -1 but yr code will give 3 .
You were very very lucky … weak test cases…

Thats why I asked for the proof in mathematical poove in above chat in this forum.

Why do we need to check that the sum of divisors =x ?..
here is is the proof for the same –Number of divisors / sum of divisors

1 Like

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.

becuz x<=1e9

try ,
1
1000000000 1000000000 1

A solution in O(1) is also possible

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}

3 Likes

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

what’s wrong with this CodeChef: Practical coding for everyone

I cant get it ? some cases passed some saying wrong answer even though i had applied same method as editorial. rechecked several times .

I realized just after the end of the contest that testcases were weak :stuck_out_tongue: and if I had got WA during the contest I would go for checking the sum :slight_smile:

For setter’s solution what is the purpose of while loop for c (c is gcd(a,b))?