Math Basics for Contests
Parity, divisibility, remainders with negatives, gcd and lcm with Euclid, ceiling division, sums of series and digit tricks.
Parity
Parity is whether an integer is even or odd. It sounds trivial, yet many 800-1000 problems reduce to it.
| Operation | Result |
|---|---|
| even + even, odd + odd | even |
| even + odd | odd |
| even x anything | even |
| odd x odd | odd |
- Test with
x % 2 == 0for even. For odd, testx % 2 != 0, neverx % 2 == 1, because-3 % 2is-1in C++ and Java. - A sum of
kodd numbers has the parity ofk.
Quick check
1 / 2
a and b are both odd. Which value is always even?
2 / 2
In C++, what does (-3) % 2 == 1 evaluate to?
1 of 8