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
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???
yes you are correct , inv(b) = inv(b % m)
let me show you an example.
2 = 9 = 16 = 23 = 30 mod(7)
inv(2) = inv(9) = inv(16) = inv(23) = inv(30) = 4 (under modulo 7)
you can prove it too using modulo arithmetic.
but you told inverse of a number n under module prime m is n^(m-2) so for 2- its 32 and for 9 its 59049?
as I explained in the video lecture , inverse modulo < m , if not you need to take their remainder with m.
clearly neither 32 nor 59049 are smaller than 7
so inv(2) = (32 % 7) = 4
inv(9) = (59049 % 7) = 4
I recently watched your video on July circuits hacker earth , where you used a line in the code for x y z path queries problem ,
- invFact[i] = (invFact[i-1] * power(i , mod - 2)) % mod;
I have been trying to figure out how to calculate inverse modulo in dp since then and haven’t figured it out yet . It would be really helpful if you could explain it here or make a video on " how to calculate modulo inverse of all positive integers up to n".
I think in lecture 15 of number theory I have explained that.
first checkout that lecture , if you still need help let me know
1 Like
Ok , so we have invFact[i] = ( Fact[i-1]*i ) ^ m-2 and Fact[i-1] ^ m-2 is invFact[i-1] so we have written invFact[i] = invFact[i-1] * (i ^m-2) . Is that right ?
Also the time complexity of this approach is O(nlog(n)) , ( if I’m not wrong ) but there’s a O(n) solution to calculate inverse modulo for a range of (1,n) , can you please explain that as well ?
1 Like
Please do an editorial video of Aug long 2020 problem “Subsequence counter”
Please make video about chinese remainder theorem, inclusion-exclusion principle etc.
plz HElp … 
this question is “Fire Escape Routes”
link: FIRESC Problem - CodeChef
sample test case is passing but while submitting it says Wrong ans …i couldn’t figure this out …
i using same method as @waqar_ahmad224
- YouTube
code is in PYTHON 3.6
submittion id : 37325098
user name: akankshaerror
Code:::::::::::::::::::::::::::
import sys
sys.setrecursionlimit(10**8)
aj=0
def dfs( node):
global aj
aj=aj+1
vis[node]=1
ln= len(li[node])
for child in range(1 , ln):
if vis[li[node][child]]==0:
dfs( li[node][child])
xx=10**5
li= [0 for i in range( xx + 1) ]
vis=[ 0 for i in range( xx + 1)]
try:
for _ in range(int(input())):
n,m = map(int, input().split(" "))
li= [[i] for i in range(n+1) ]
vis=[ 0 for i in range(n+1)]
for i in range(m):
a,b= map(int, input().split(" "))
li[a].append(b)
c=0
res=1
for i in range(1 , n+1):
if vis[i]==0:
aj=0
dfs(i)
c=c+1
res= (res % (10**9+7) * aj% (10**9+7) )% (10**9+7)
print(c , res)
except:
pass