The trick from 5:19 is useful only when you solve this problem with pen and paper (e.g. during a math test). If you have a computer or calculator then ignore that trick and just check values one by one even if they're big. I added English captions, enjoy!
To the point, direct and efficient. No BS. Thanks Errichto. After spending countless hours on YT viewing CRT doing ages old methods and bookish stuff, finally I came across a logical solution to it. :)
Although I am not in a college yet but still beside doing Phy/Chem/Maths... I enjoy your videos.. thanks for making things simple for me to understand.
Wow, nicely done! This was quite intuitive and easy to understand. Of course you need more for big mods but this is a very helpful intro, and the explanation was super clean!
It's even quicker if you notice that 3 ≡ -1 (mod 4) and 5 ≡ -1 (mod 6), So x = -1 satisfies the first two congruences. The lcm(4, 6) = 12, so the solution will satisfy x ≡ -1 (mod 12) Also if x ≡ 2 (mod 5). then x ≡ 2 or 7 (mod 10). So we're looking for a number that is 1 less than a multiple of 12 and ends in 2 or 7 i.e. find a multiple of 12 that ends in 3 or 8, It only takes a moment to spot that 48 is a multiple of 12, and so 48 -1 = 47 will satisfy all three congruences, as will all x ≡ 47 (mod 60) - the lcm(4, 5, 6). It shouldn't take 2 minutes.
I know it might not be important for all but can you please have lower resolutions other than 1080p on your twitch streams. It helps a lot but I have a limited amount of data
Pl read Liber Ulbrict Libberchit . Thirteen Century Chinese Remainder Theorem. What u have done is Brahma gupta ' s theory of 600a d from India. in C R platform. Good Idea. .Merging
x = 3 (mod 4) x = 5 (mod 6) x = 2 (mod 5) In my opinion it is not good example for the beginning with Chinese Remainder Theorem x = 3 (mod 4) x = 1 (mod 2) x = 2 (mod 3) x = 2 (mod 5) x = 3 (mod 4) x = 2 (mod 3) x = 2 (mod 5) x = 3 (mod 4) x = 2 (mod 15) 1 = 4*(4)+15*(-1) x = (4*4*2 - 15*1*3)(mod 60) x = (32-45+60)(mod 60) x = 47 (mod 60)
@Errichto, i need your help friend, can you please make a video on -> how to calculate product of divisors for very very large numbers(represented by prime factorisation). you can refer to problem cses.fi/problemset/task/2182/ which is a newly added problem to cses, thanks :)
The trick from 5:19 is useful only when you solve this problem with pen and paper (e.g. during a math test). If you have a computer or calculator then ignore that trick and just check values one by one even if they're big.
I added English captions, enjoy!
Just the other day, I revised modulo. This is perfect timing. Thanks
I enjoyed indeed.
you are a genius can you give me some tips for gamer like me just started learning coding
Thank you so much, this makes my code very efficient
This guy remembered his TH-cam password finally
Come on, once per two weeks isn't that bad!
Not that bad, but you've been doing better before
@@Errichto I fine with it. You're doing great Kamil 🙌🏻
@@mariansoltan1318 you should be grateful he's taking out of his time to teach us beginners how to do things that are like hello world to him
@@slx0371 Yes Errichto is considered to be a saint
To the point, direct and efficient. No BS. Thanks Errichto. After spending countless hours on YT viewing CRT doing ages old methods and bookish stuff, finally I came across a logical solution to it. :)
You deserve more subs bro, you explain even better than the professors.
i was watching a video that I really want to continue watching but i couldn’t help not clicking on the notification
Although I am not in a college yet but still beside doing Phy/Chem/Maths... I enjoy your videos.. thanks for making things simple for me to understand.
Wow, nicely done! This was quite intuitive and easy to understand. Of course you need more for big mods but this is a very helpful intro, and the explanation was super clean!
i just found out i independently invented chinese remainder theorem to solve a task for advent of code 2020
Well done, may Allah guide you and us to the truth.
@@عَدِيُّ-م3ح wtf??
@@erenyeager4452 May Allah guide Eren Yeager as well
OMG You are such a God I would say you make a full tut series on algorithms
True
@Ameen Sha C It's just a metaphor.
@Ameen Sha C Calma
@Ameen Sha C LOL You took it on your heart
@@techwithgantavya6381 He was furious last night, ;)
I already watched so many videos about CRT but you only explained how to solve it in 2 mins. Thank you, done subscribing.
Thank You Bro, I have a DM exam tomorrow, this will save me time
I didn't knew this; it feels like a game, thanks for sharing and for nice explanations.
Man iam big fan from Egypt you my inspiration specially on competitive programming keep going ❤❤
Your videos are really helpful
Hope you will continue uploading more frequently
It's even quicker if you notice that 3 ≡ -1 (mod 4) and 5 ≡ -1 (mod 6), So x = -1 satisfies the first two congruences. The lcm(4, 6) = 12, so the solution will satisfy x ≡ -1 (mod 12)
Also if x ≡ 2 (mod 5). then x ≡ 2 or 7 (mod 10). So we're looking for a number that is 1 less than a multiple of 12 and ends in 2 or 7 i.e. find a multiple of 12 that ends in 3 or 8,
It only takes a moment to spot that 48 is a multiple of 12, and so 48 -1 = 47 will satisfy all three congruences, as will all x ≡ 47 (mod 60) - the lcm(4, 5, 6).
It shouldn't take 2 minutes.
awesome stuff, way more efficient than what uni taught me
Thanks for the video ! You actually are the only ytbers where i have notifications on haha.
You are amazing !
Thank you so much. It's a nice explanation with detail. I enjoyed your content!
Thanks a lot for the video Errichto. Hope to see more video in this channel as well.
man, you literally just save me from failing my term exam
This guy seems good at maths, he should try programming or smth.
Lol😂😂
7:16 nicee
Please make a list of important data structures that we need to learn to ace in competitive programming
I know it might not be important for all but can you please have lower resolutions other than 1080p on your twitch streams. It helps a lot but I have a limited amount of data
Nearly the end of January and he still has his Christmas hat on. LOL.
Trust me, if you don't tell him, he won't change it himself
I think there is a necessary condition that every pair of moduli must be coprime, so we can use extended Euclidean
You should start algo and ds series
Hope you would 👍
A video on fourier transform please :)
MAN U R A GODD MATHEMATICIAN
More of these please
nice to see ur new video here erichto, we miss u here lmao
I to jest dobry content, bez cpp! :)
thankyou so much errichto.
YOU ARE AWESOME BRO ALSO NICE GUY
that helped me AF thanks budd
this vid saves my dm exam :')
Great explanation!!
thank you very much!!
Im proud you are polish.
nic z tego nie rozumie, ale jestes kozakiem w tym co robisz...
고마워요=thank you
after so long you have uploaded a video.
Thanks Erichto!
What to do to get a heart from errichto.....🤔🤔
awsm trick sir ji
From Atcoder's contest
Errichto, would you consider to make videos on computational geometry !!
Thanks brother
Hi, can you make a video on adaptive huffman coding? I would be very grateful :-)
381 is the answer a little bit after timestamp 6:30, I computed it myself
Nice!
Very good
Thank you
Errichto🤩
Beautiful
Can you please tells what is the best way for programmers to become good in math.
What if one of the system is
X = y mod8 ?? How can we solve that?
Like X = 2mod12
X= 8mod30
X = Cmod20
How can i get C??
Irony is that this works drastically slow for large values and we have to switch back to Extended Euclid algo.😀
thanks
GOD
What drawing tablet do you use? Thank you.
Only educational videos can get that kind of ratio of likes compared to dislikes.
Is it possible to solve this problem faster?
Can you help me with this, please:
x ≡ 2 (mod 11)
x ≡ 9 (mod 15)
x ≡ 7 (mod 9)
x ≡ 5 (mod 7) ?
please provide amazon link of the chair you've got
Pro Polak programista ;)
Wich program did he use for his presentation?
Pl read Liber Ulbrict Libberchit . Thirteen Century Chinese Remainder Theorem. What u have done is Brahma gupta ' s theory of 600a d from India. in C R platform. Good Idea. .Merging
How did discover this technique
where are you bro i even forget you exist
He is teaching us from competitive programming handbook 😅😅😅😅 , i know him very well 🤭🤭🤭
Is this method described in CPH?
@@Errichto yes i think
Where are u from man?
buenardo
Do you have discord
Still waiting for gausian elimination 😶
x = 3 (mod 4)
x = 5 (mod 6)
x = 2 (mod 5)
In my opinion it is not good example for the beginning with Chinese Remainder Theorem
x = 3 (mod 4)
x = 1 (mod 2)
x = 2 (mod 3)
x = 2 (mod 5)
x = 3 (mod 4)
x = 2 (mod 3)
x = 2 (mod 5)
x = 3 (mod 4)
x = 2 (mod 15)
1 = 4*(4)+15*(-1)
x = (4*4*2 - 15*1*3)(mod 60)
x = (32-45+60)(mod 60)
x = 47 (mod 60)
Needed a competitive coding partner with whom I can start my competitive coding journey .Anyone interested please reply?
@Errichto, i need your help friend, can you please make a video on -> how to calculate product of divisors for very very large numbers(represented by prime factorisation). you can refer to problem cses.fi/problemset/task/2182/ which is a newly added problem to cses, thanks :)
Use the fact that these are multiplicative functions.
This might help:
cp-algorithms.com/algebra/divisors.html
damm
Make more algorithims videos
Sup
You are talking about code many times during video, haven't you tried once actually coding in your life ????
When and where this algorithm is used ?
Can anyone help 🥲