Computations Modulo P in Competitive Programming

[@abhishek.rathore]

You are developing a lot as a Content Creator. I love that. Also that new background looks dope.

[@BuciuEmilian]

I agree. He definitely evolved a lot in the past 6 months as a content creator. I also like that some of his videos get humorous.

[@mdisrafil2491]

Soon you will get 10^9+7 subscribers

[@zinyang8213]

% M :D . Thanks Errichto, your content has been a godsend blessing :)

[@aniketash4738]

@Kane Sonny you have to give money right ? in instapwn i tried they were asking to pay money

[@keshavbansal6343]

He had more than a billion it just got modded

[@sayanghosh6996]

these videos packed with valuable information are way way better than the 'influencer' videos by other channels which dont actually help you learn anything. Thanks for this!

[@shresthmishra9329]

For those who only want to know about how modulo works with division or inverse can directly skip to 10:50. Thank you @errichto for investing your time and making us understand easily.

[@RamisaAnjum]

You look pretty relaxed all the time! It inspires me to learn more and more.

[@lucasnogueira3232]

Errichto youre amazing, your youtube channel is the best in cp

[@АлекСневар]

Guys, I think we should really appreciate these brilliant pieces of knowledge and experience which the man shares with us. Thank you so much, Errichto

[@farazamir-mi7et]

GOOD saying I also love that best of luck

[@mizel_almizel]

All programmers bad teachers only Errichto he the best programmer and best teacher Always He said just practice so everyday I grow thank you bro I love you u change me forever ♾

[@shaswatlenka1416]

How in this world are you so composed all the time! That's something we all need to learn!

[@parthsalat]

Very true!

[@aryankumar87771]

genius man, they way of ease of explanation is unparalleled on yt

[@PankajKumarGladiator]

Appreciate your explanation on modulo operations. This will definitely help me to solve problems with more precision. Expecting for more future lectures like this. Keep it up !! And nice background 👌

[@bhaaratkumarkhatri4834]

u r geniusssssssssssss bro thuanku............. i am stuck at the problem from 4 days ................it is solved nowwwwwwwwwwwwww

[@dinohunter7176]

I managed to follow the logic, but unless I don't try it in coding, I'm not confident I've understood perfectly. Thanks for new insight of hacking numbers faster.

[@divyanshu8874]

Besides you are such acclaimed programmer, You are so humble and simple❤️❤️

[@society183]

I hope to see u doing more of these educational topics as these are easy to understand and learn...

[@vaibhavjadhav8987]

This guy really deserve Millions of subs💯💯

[@creativegiant148]

I liked when you said we should try to make languages equal in cp. I feel this problem a lot in cses i do it in java and its real hassle over there i need to 100% optimize my code to get selected, while the same less optimized algo work fine in cpp When i tried to tell this thing in one of cf blog everybody criticized me and they all devoted(so now im a newbie with -5 contributions) but now i feel lit good

[@GameplayForNarration]

this is awesome errichto😃. it’d be cool if you made videos like this on other topics from the competitive programmers handbook, or just books in general. 👏🏻

[@nelsonthekinger]

I only saw this requirement once in a question, it was today and i was confused. This video helps. Lot! Thanks!

[@vms_kt]

Thank you very much for the explanation. By far the easiest one to understand why and how to implement the modulo in coding contests.

[@mihirbhasin1970]

Bro you are such an inspiration to me ❤️

[@akakop]

@@audiogear4412 what are u getting from benq and 7k+? Atleast this guy is doing something for u.

[@audiogear4412]

@@akakop My bad.

[@akakop]

@@audiogear4412 np

[@Grassmpl]

Z/nZ forms a ring with the natural addition and multiplication of cosets well defined. If n is prime, we get an integral domain which make hashing very convenient especially with double hashing with a constant secondary hash function.

[@praveenawesome2182]

Thanks erricto for such awesome content being a pupil on codeforces ,these videos motivates me to do a lot better and try to jump to candidate master one day !!

[@thamidurandilbandara415]

you can do it! best of luck! ( i am also trying :D )

[@hackerencrypted8234]

Hey Errichto, this was very basic introduction to modulus operator. I was able to learn this on my own when i was a super beginner.I ll be happy to see something more advanced something which troubles me a lot like using modulus to calculate inverses till n in O(n) time. I saw there was some tough formulae on that (a pretty long one) which i could not understand how it works. Your content is quite good for people who are beginning. But please for people like us who are stuck in ratings like 1500-1600 on cf , please add some intermediate stuff too, maybe some advanced DS too. Go on with your great work! GL!

[@lawbindpandey402]

Well he can't solve a specific problem !! So he teaches the basics and the later can be learned !! If you want the other way (specific problems) you can view his other channel errichto 2 where he does long stream !!! If lucky enough you might get solutions of some contest that you might be participating in, even the "F" problems !!! Any way you can always find editorials for standard problem !! And as you say you are 1500-1600 on c.f you'll be well good to figure it out yourself!! Just try for 2hrs max for "F" problems and you'll be there .....

[@hackerencrypted8234]

@@lawbindpandey402 i know that bro! I am not asking for solving specific problems.I am asking for some intermediate concept. Solving F is a bit too far for me. In div2 i usually do 3 out of 6.Where did i ask to solve some specific problem?? I requested for some generic intermediate stuff.

[@hackerencrypted8234]

@@lawbindpandey402 I am happy you replied, but please read and understand what one wants to convey and then reply.I used the word "like " which according to me suits when you are giving an example and not for specificity.

[@lawbindpandey402]

@@hackerencrypted8234 Aah!! got you bro !! Sry for bothering you ...😇😇😇...Any way it's always easy to explain some concept with litter example and so he did !!! and once again my apologize !!!😇😇😇

[@hackerencrypted8234]

@@lawbindpandey402 why you are apologizing dude! no way! its perfectly okay buddy!! I am from India doing my standard 11th right now! I have a lots of respect for you bud!! keep on with good work! Ciao Adios!!

[@arthak2475]

It's so good to see that you recommended CSES Problemset. Cause I did say that in one of the comments that sent you, feels like i recommended it :p Great Video btw.

[@Errichto]

I know CSES problem set from an announcement blog on Codeforces... where I then complained about too many websites and said this is unnecessary :D

[@arthak2475]

@@Errichto I know that you must have already knew about it.

[@arthak2475]

@@Errichto Everything must seem unnecessary when you're at a level that you're at. 😬

[@ChandraShekhar-by3cd]

This has REVEALED the SECRET of (10^9+7) . I was always thinking that it is a random sort of fancy thing that all competitive sites are using. Thanks a lot Errichto for CRYSTAL CLEAR Explanation.

[@nextrie]

Once again, I learn something new from you. Thanks so much.

[@deeptendusantra670]

Your explanation of codes is very insightful.Loving your content.♥️

[@karimfathi1955]

this is very useful for beginners competitive programmer , please make a lot of videos for us.

[@arinroday302]

Just keep it up Errichto. Excellent as always

[@kimjong-un4521]

we are so lucky to learn from you.

[@williamwambua7710]

Thanks ....Errichto this site has every thing organized

[@TahsinAhmed-yj9ns]

to the point video, need these videos more , as always great content

[@harinath_mishra]

This was very great video errichto sir .I would love to watch your video Editorials of Contests.

[@katakamsaiteja7934]

your content is gold.

[@Errichto]

Thank you :)

[@tomtan298]

Awesome Video! I can see a great potential in you to be a awesome youtuber! Would be nice if there were slightly more tutorials on entry to intermediate questions and concepts used in CP.

[@tomtan298]

Or maybe a beginner - intermediate stream

[@ashuadhana1840]

@@tomtan298 this is actually one of the very basic things in cp , i think many people in cp may not even talk about it ,it's that basic

[@parthsalat]

For errichto, even coincidence is a power of 2

[@parthsalat]

Thanks for the video. And oh, did I mention you are no less than a God?

[@miteshkumar3183]

A topic you could make a couple videos about is Digit DP. There aren't many good explanations online about this. This is a technique to solve questions that involve counting numbers within intervals with certain properties. For example, Given to very large numbers as strings L and R, and an integer K, count how many numbers from L + 1 to R inclusive, that have exactly K non-zero digits.

[@ashutoshsanodia5690]

Very valuable info errictho

[@sourabhjagtap4950]

Very nice explanation !! Keep on doing what you do, and thanks for sharing !!

[@simone8504]

This helped me a lot with modulo operation, thank you very much !

[@darkcry69]

We need a tutorial on graphs

[@adityasoni6966]

Great Video!! Waiting for the PART-II.

[@sharinganuser1539]

I learnt the subtraction and division part the hard way...when I was implementing some rolling hash function....inverses can also be good... P.s I commented at around 9:00..I should have seen the whole video first..

[@shaswatlenka1416]

Keep making awesome videos! Love these!

[@mokshchadha9151]

you are awesome errichto maybe someday i will be a better coder too, keep making such lessons

[@AbhishekKumar-hj4qo]

You are the best @Errichto.. many might have more knowledge but you are the one who shares it... And that differentiates you from others.... BEST OF LUCK FOR CODEJAM ❤️ #love_from_India ❤️

[@abhishektangod657]

I loved the new background 😍

[@rajmittal5394]

i am solving some question and there given modular division , i think that it is like a regular modulo but this is something new for me

[@abhishekshaw21]

Your videos on April leet code challenge were amazing kindly do it again for June.

[@occo5877]

Please do leet code challenge June !!! You don’t need to put the video up the same day since you said it’s tiring. Pleaseeee! You r super helpful!

[@pallab900]

Thank you for this. This lecture was very enlightening

[@sanchitchakraborty8146]

You really are keeping me motivated

[@subham-raj]

I wanted this from so long :)

[@Crytoma]

long long*

[@rishavmasih9450]

This stuff is a recreational drug.

[@xssimposter5203]

For those interested in the modulus calculus and the tricks he discussed with Euler's formula. I would recommend reading a cryptography book. You learn some clever tricks with prime numbers and modulus.

[@xssimposter5203]

Understanding Cryptography by Christof Paar has a great web series to go along with the book.

[@lovvyparhar393]

loved the new background!

[@manjunathvasam4981]

There is this set of problems based on calculations involving doubles. Could you make a video on this if possible?

[@jimwoodward7293]

Great lecture -- great content!! Thanks.

[@AmitSingh-cs2hb]

Nice explanation brother😍😍

[@luanaamorim5055]

Your videos help me so much, thanks!

[@harshit.jindal]

Great explanation. Thanks a lot. Subscribed!

[@chaitanyakumar9229]

Now beginners like me can also watch ur videos 😅😂

[@akhilarya7517]

how are 4 and 10 coprime ? 11:47 please someone clarify

[@32Praful]

They are not coprime. 4 is number of coprime numbers between 1 and n(10). Google euler's totient function.

[@suryanshchaturvedi1391]

Bro please make more videos on Mathematics. Keep up the Good Work.

[@AbelShields]

At 9:30, can you instead have (a - b + MOD) % MOD? That would be a little simpler.

[@alferidmokhammed4958]

Nice video! It would be nice if later you could cover more advanced algorithms like baby-step-giant-step.

[@saikatkarmakar389]

I really liked your problem solving approach. Any tips on how to be a better competative programmer ☺️☺️

[@syed7996]

I'm not able to understand, how you choose 4 as co-prime for 10 as co-prime numbers have only 1 as their common factor. Please help me understanding better. Please explain the part --> b power (co-prime of mod (smaller than mod) - 1) thank you @Errichto Please reply

[@willrumble510]

4 is wrong. Look up the Euler Totient function online it will explain more

[@xbaphomet0136]

nice tutorial

[@hafiz031]

Can taking modulo M ensure the program would have produced correct results if we didn't take the modulo? As taking modulo with M will only produce results in [0, M-1] range. So, there might be some case, where two implementations (one is correct, and another is wrong) of the same problem might give the same results when we take the modulo and can bypass the test cases.

[@rudy650]

Why would you want to modulo a-b or a/b , considering answer will be smaller than 'a' and can be stored in whatever a was stored in?

[@prashantkumar2963]

Thank you Errichto.

[@Yash_Shende]

TBH you are GOD in CP

[@shanewalsch]

3:45 isn't it better to use ((x % c) * (i % c)) % c, so we won't get an "i" number overflow?

[@DinoOnBike]

That background is soo dope

[@abdelrahmanyehia562]

This was very helpful!! Thanks you.

[@RailSuleymanov]

I completely missed the division part... idea given in the video seems to be working for case a = 8, b = 7, but author doesn't use the formula he wrote in the code for "divide" function. The plugged variables from the examples would be a = 8, b = 7, p = 10, right? Or p = 4 because it is co-prime of 10? In either case the function divide wants the p - 2 as power, but he uses 4 - 1 = 3. Very confusing.

[@nelsonthekinger]

I like the fact you code and can explain well. Many times very good cp guys explain very bad :)

[@tusshar2000]

For python multiplicative inverse can be calculated by pow(p,mod-2,mod)

[@mohamedtamer9041]

Thanks. Good explanation 👏

[@sauravkumarjha2838]

here in division modulo computation, (28/7) % 10 gives correct result. here 28 is divisible by 7 but what if it is (29/7) % 10, it doesn't work. any thoughts?

[@em_nikhil_007]

Exactly i was looking for it . Are you listening to my mind?

[@i.anandsingh]

Well am a beginner as well but the ans of trailing zeroes i suppose is the number of multiples of 5 upto n because they are the ones that add extra zeroes at the end.

[@OneWayReality]

Euler's theorem only holds true for the relation b^(p-2)=1/p only if b and p are both prime numbers. So from my observation, I think, we can't use [int divide(int a,int b)] function all the time, only if b is a prime number then only we can apply that Euler's function......

[@imsuck12]

You're confusing Fermat's little theorem with Euler's theorem. Fermat's little theorem states that b^(p-1)=1 (mod p) (for prime p). Whereas Euler's theorem is a generalization of Fermat's little theorem: b^φ(m)=1 (for coprime b, m).

[@Anveshana837]

In the substraction part do we need the last modulo ? the answer will be always less than the modulo so I don't think we need the last modulo which you added, it is just redundant. Please correct me if I am wrong.

[@systemflaws]

Nice and Smooth explanation. I love your tutorials. One day, I will become a red coder. Give my 110% to this journey.

[@saksham9170]

I highly doubt it. Most people who become red love to solve problems rather than commenting on a video about becoming red.

[@ganeshchowdhary3024]

At 15:58 it is while loop , not if

[@tirthjayswal9895]

Best Explentation on MOD ..Thanks

[@stabgan]

This video was very helpful. Thanks

[@abdellatif_anaflous]

Keep going bro my eyes on u

[@googool.3769]

Just wow ❤️

[@DarshanLokhande]

Hi Errichto, the thought just popped in my mind that if a= 34,b = 12 , MOD = 11 , then the faster function mentioned at 16:01 would return 35. How do we handle such cases in the faster function ?

[@arthak2475]

It's assuming that a and b are less than equal to modulo or if you feel they're gonna be bigger just take a%mod + b%mod

[@LongLiveIsrael-c7y]

Can someone please explain why when doing the 1000! at @01:00 we get so many 0's in the end of the number?

[@xbaphomet0136]

zero is a result of 5 * 2, just calculate how many fives are there in that factorial

[@alankritanand5400]

Can u please make a video on pbds

[@udaypatidar5183]

You are rocking us

[@notabot8909]

Do you recommend only reading the editorial and not implementing the solution in the hope of getting exposed to more ideas/problems? Or does it not matter at all? I read your FAQ and couldn't find this question

[@sauravpandey599]

A great fan of yours

[@kenichimori8533]

Modulo 0P = Modulo 0P rational behind solid works. Entoropy 0 = 00 = 000 = 1 = 2 = 3 Zeros size line of doze. G Thanks.