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.

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 ?

Please do an editorial video of Aug long 2020 problem āSubsequence counterā

https://www.codechef.com/problems/SUBSFREQ

Please make video about chinese remainder theorem, inclusion-exclusion principle etc.

plz HElp ā¦ this question is āFire Escape Routesā

link: https://www.codechef.com/problems/FIRESC

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

https://www.youtube.com/watch?v=0vsLTnXgsyo&list=PL2q4fbVm1Ik6DCzm9XZJbNwyHtHGclcEh&index=13

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

hey,i have used same logic as u taught,but i am getting TLE.why>???

here is my code,

n,q=map(int,input().split())

def factor(n):

res=[]

i=2

total=1

while i*i<=n:
if n%i==0:
c=0
while n%i==0:
c+=1
n//=i
res.append([i,c])
total*=(c+1)

i+=1

if n>1:

res.append([n,1])

total*=2

return res,total

def common(n,res,k):

ans=1

for i in res:

c=0

a=i[0]

while k%a==0:

c+=1

k//=a

ans*=(min(i[1],c)+1)

return ans

res,total=factor(n)

for i in range(q):

t,k=map(int,input().split())

if t==1:

ans=common(n,res,k)

print(ans)

elif t==2:

if k>n:

print(0)

else:

ans=1

for i in res:

c=0

a=i[0]

while k%a==0:

c+=1

k//=a

if c>i[1]:

ans=0

break

ans*=(i[1]-c+1)

if k>1:

print(0)

else:

print(ans)

else:

if k>n:

ans=0

else:

ans=1

for i in res:

c=0

a=i[0]

while k%a==0:

c+=1

k//=a

if c>i[1]:

ans=0

break

ans*=(i[1]-c+1)

print(total-ans)

G(1) = 1, G(2) = 1. G(n) = aG(n-1) + bG(n-2) + c. Suppose this is our recurrence relation then?

hii im getting wrong answer when i submit using sieve in this code can you help pls

problem link :

spoj etf

mycode: ideone link

In [SPOJ.com - Problem PRIME1] while initializing the sieve, why did we write

if(i != p)

https://youtu.be/26q-qr9FcHo?t=328

Please explain. Thanks.

@waqar_ahmad224 can you tell me why i am getting TLE in this submission

https://www.codechef.com/viewsolution/47359228