thanks a lot man
Hey bro , i think you need to start a series on mobius function since it’s used in many GCD problems
brother ,when we get next video on number theory
Now that you ask , I think in less than 2 days
on which topic u r working for next video ? any hint
teaching importance of prime factorization.
Q. how to find number of common divisors of 2 (N and M) Numbers quickly (like in O(logN)) where there are Q queries N remains same and M change.
N <= 10^12
M <= 10^12
Q <= 5 *10^5.
Can anyone help me with this problem? It require precomputation to find the depth of ETF. I am getting WA,please help!
upload all the videos plz
Precompute all values.
check my code if u want https://ideone.com/saPHae
I will for sure
i was trying something similar to this!
thanks a lot for your help
30 June 2020 : 1 new lecture added
L23 : Finding Number of common divisors in O((LogN)^2) Time
Nice video. But shouldn’t the time complexity be O(logN) only instead of O(logN)^2?
Because the number K can’t be divided more than logK times. So the outer loop will run logN times and the condition inside this loop should only be satisfied at max logK times. So, according to my understanding it should be O(logN + logK) per query.
ohhh f*ck yes.
when I prepared the PPT I knew this fact so in the video there is written complexity LogN , then after some days when I started recording video during recording I was like hmmm there 2 nested loop each running roughly logN time so complexity must be LogN^2.
and Now I messed up.
Haha… Happens with the best of us.
thanks for pointing it out btw , will make a 2-3 minutes video explaining complexity this time
sir, after watching the lecture, i submitted kth prime number(TDKPRIME) problem. Then i went for the problem KPRIMES2(hard) on SPOJ itself, it is giving runtime error at the last testcase.
please help me to optimize the code.
I haven’t solved this problem yet , but this seems an interesting problem.
Don’t worry I will be posting solution for this in 1 or 2 days
15 July 2020 : new video added
E001 : Queries about Numbers (Medium) | Codechef
in lecture 15 how come (n! / c! * r! ) % m = (n! % m) * ( inverse( c! %m ) %m * ( inverse( r! %m ) %m
inverse(c!)%m is fine but how come inverse(c!%m)%m because in factorial funtction we are always taking %m when multiplying.
so according to this inv(b) = inv (b%m) where b is any number and m is for modulo???