Intro
Addition modulo p is simple, just add the two numbers, then modulo the result. Multiplication is also simple — multiply then take modulo. However, subtraction cannot be done in this way. This caught out quite a few people in today's Educational round due to the weak pretests on problem C, and I wanted to make a blog about it so that hopefully this doesn't happen again.
The pitfall
Take this: 306786744 submission for example. There were plenty that did exactly the same thing, but I just picked this one because it's relatively short. Specifically, let's look at the following line of code:
ans = (ans+one-onemain)%MOD;
You might think — what could possibly go wrong here? You're just adding and subtracting some numbers and taking modulo. Quite a lot as it turns out. The issue is that in C++, the modulo operator does not work well with negative numbers, and will just give you a negative remainder. This causes a problem because when I carefully (read: ask GPT to) construct a countertest, I can exploit this incorrect behaviour of the modulo operator, and cause your code to output the wrong answer. The way it's done is that I try to create a testcase where onemain is large, and ans+one is small (in this case, has just been wrapped round by the modulo operator). Now, we've got a negative number, and we take modulo, so now the calculation just outputs a negative number and you got hacked.
How to ensure this doesn't happen to you?
Two ways:
Make sure to add MOD after subtracting two numbers, then take the modulo of the result. If we correct the code to
ans = (ans+one-onemain+MOD)%MOD;, everything passes.Just use a modular arithmetic template. It comes up in so many problems, so I think it's a waste of time writing all this MOD stuff out every time, and it could save you a lot of WA, or if you're REALLY unlucky like today, FST.
Hope this helps someone!
