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

tutorial
, ,
104

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.

105

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?

106

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

107

2 Aug 2020 : new practice problem added
E004 : LCM Sum | Spoj | Number Theory

1 Like
108

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".
109

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
110

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
111

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

:slight_smile:

112

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

113

plz HElp ā€¦ :pray: 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

114

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

115

Can You please Create a PDF of practice Questions that cover all the topics. :pray::pray:

116

Just a suggestion, can you make your presentations in dark theme?

117

@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.

118

Pls dont forget the course im impatient for learn pollar rho algorithm

119

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())

find the prime factorization of n

def factor(n):
res=[]
i=2
total=1
while ii<=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

common divisor

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)

120

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

121

hii im getting wrong answer when i submit using sieve in this code can you help pls
problem link :
spoj etf
mycode: ideone link

122

In [SPOJ.com - Problem PRIME1] while initializing the sieve, why did we write
if(i != p)
- YouTube

Please explain. Thanks.

123

@waqar_ahmad224 can you tell me why i am getting TLE in this submission
https://www.codechef.com/viewsolution/47359228