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
Hey I need help in this problem
In this problem you have made a video covering the case where mod>=N but what to do when mod<= N as in this case given mod is 1009
Can You please Create a PDF of practice Questions that cover all the topics. 
Just a suggestion, can you make your presentations in dark theme?
@wakar_ahmad224 you show how we how calculate gcd sum like (gcd(1,n)+gcd(2,n)+…+gcd(n,n)).
but i want to calculate lcm sum. Given N and find lcm sum like (lcm(1,n)+lcm(2,n)+…+lcm(n,n)).
how can i approach please help me out anyone. TIA.
Pls dont forget the course im impatient for learn pollar rho algorithm