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

tutorial
, ,
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

124

in fermat’s primality test :-
in this int a = 2 + rand() % (n - 3);
how doing modulo with (n-3) resulting a in range [2,n-2]?

125

Hey Waqar! I have a doubt from L15: Binomial coeff. using Modulo Inverse.
The return type of power in that program is ‘int’, however in the code of the function we are converting res to long long by multiplying it by 1LL. So why does the compiler not give any error? Thanks in advance.

126

Please make video on Chinese
remainder Theorem .