Number theory course : youtube CodeNCode(2 Aug 2020 : Practice Problem added)

thanks a lot man :+1: :slightly_smiling_face:

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

1 Like

Now that you ask , I think in less than 2 days

on which topic u r working for next video ? any hint :wink:

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!

Thank you!

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

1 Like

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.

1 Like

yup.
thanks for pointing it out btw , will make a 2-3 minutes video explaining complexity this time

1 Like

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

1 Like

15 July 2020 : new video added
E001 : Queries about Numbers (Medium) | Codechef

1 Like

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???