Crt linear congruence

#1

Sir I am doing wrong in finding multiplicative modulo inv.
please sir check my code and tell me how can I find it correct.

#2

Hello @yashme7125 please wait let me check your code I will get back to you.

#3

@yashme7125 the majot mistake you are doung is that you are taking the input in the wrong format: like you cant take the input for both the arrays simultaneously like you are doing.
check this corrected code:

#4

Sir thanks for correcting the code but how did you did you know that gcd of pp(i) and num(i)
will always be 1 in order to find multiplicative modulo inv(i) because in order to find it gcd(a,m) should be 1 ?

#5

@yashme7125 have you seen the editorial for this?
the operation i have done in the back calls of recursion are handling the actual values only.
we have taken the case when bill become zero at certain point as we are taking modulus there then when b will become 0 then only we will make x=1 and y=0 .

#6

Sir I want to say that when we are calculating multiplicative mod inverse the gcd of a and m should be 1 but in crt how would we know that gcd of pp(i) and num(i) is 1?

#7

@yashme7125 no no in congruent we have started from 1 and then we will give a try by taking 1 as 1 to sabka hoga hi

#8

Ok now ab samjh aaya

#9

@yashme7125 if you feel that you doubt is clear you can mark this doubt as resolved.
Happy learning!!

#10

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.