Modular arithmetic
#include <iostream>
using namespace std;
const long long MOD = 1000000007;
long long power(long long a, long long b) {
long long result = 1;
a %= MOD;
while (b > 0) {
if (b & 1) result = result * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return result;
}
int main() {
cout << "2^30 mod p = " << power(2, 30) << "\n";
long long inv3 = power(3, MOD - 2);
cout << "1/3 mod p = " << inv3 << ", check: " << 3 * inv3 % MOD << "\n";
long long a = 3, b = 5;
cout << "(3 - 5) mod p = " << ((a - b) % MOD + MOD) % MOD << "\n";
return 0;
}When answers are huge, problems ask for them modulo MOD = 10⁹ + 7. Addition, subtraction and multiplication can all be done modulo MOD as you go:
(a + b) % MOD, and(a * b) % MODwithlong long(each value is below MOD, so the product fits);- for subtraction,
((a - b) % MOD + MOD) % MOD, because%of a negative number is negative in C++; - fast power
power(a, b)squares and multiplies: O(log b). By Fermat's little theorem,power(a, MOD - 2)is the modular inverse ofa, which lets you divide.
gcd, lcm and the sieve
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
int main() {
int n = 30;
vector<bool> composite(n + 1, false);
for (int p = 2; p * p <= n; p++)
if (!composite[p])
for (int m = p * p; m <= n; m += p) composite[m] = true;
for (int i = 2; i <= n; i++)
if (!composite[i]) cout << i << " ";
cout << "\n";
cout << "gcd(84, 36) = " << gcd(84, 36) << ", lcm(4, 6) = " << lcm(4, 6) << "\n";
return 0;
}gcd(a, b)andlcm(a, b)are in<numeric>(C++17);__gcdis GCC's older name.- The sieve of Eratosthenes with
vector<bool>finds every prime up to 10⁷ in well under a second. It also gives the smallest prime factor of each number if you store it, which factorises any number quickly.
| Need | Tool | Cost |
|---|---|---|
| a^b mod p | fast power | O(log b) |
| divide mod p | multiply by power(x, p - 2) | O(log p) |
| all primes ≤ n | sieve | O(n log log n) |
| gcd / lcm | Euclid | O(log min(a, b)) |
Quick check
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.