An overview of the number theory topics that appear most often at the district, national and SIO (Serbian informatics olympiad) level: divisibility, prime numbers, GCD, modular arithmetic and fast exponentiation. Every topic has a short reminder and a link to a detailed lesson; modular arithmetic is explained here in full.
Before you start: prerequisites – Mathematical algorithms. How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.
Divisibility and remainders
The number a is divisible by b if a % b == 0. The remainder of division is the basis of many tasks: the digits of a number (% 10), parity (% 2), cycles (the day of the week is % 7). Careful: in C++ the remainder of a negative number is negative (-7 % 3 == -1), so for the mathematical remainder you write ((a % m) + m) % m.
All the prime numbers up to 107: the sieve of Eratosthenes, complexity O(n log log n).
Factorising into primes and the number of divisors: if n = p₁^a₁ · … · pₖ^aₖ, the number of divisors is (a₁+1)·…·(aₖ+1).
GCD and LCM
Euclid's algorithm: gcd(a, b) = gcd(b, a % b), complexity O(log min(a, b)). The LCM is a / gcd(a, b) * b. C++17 has ready-made functions gcd and lcm (the header <numeric>). In detail: Finding the GCD and LCM.
Modular arithmetic
When the exact result is huge (the number of paths, the number of arrangements…), the task asks for the remainder of division by some number m, most often 109 + 7 (a prime number). These rules hold:
(a + b) mod m = ((a mod m) + (b mod m)) mod m
(a − b) mod m = ((a mod m) − (b mod m) + m) mod m
(a · b) mod m = ((a mod m) · (b mod m)) mod m
That is why the remainder is taken after every operation, so intermediate results stay small. The product of two numbers smaller than 109+7 is smaller than 1018 and fits in a long long.
Division does not work by the same rule. Instead of dividing by a, you multiply by the modular inversea⁻¹ – the number for which a · a⁻¹ mod m = 1. When m is prime and a is not divisible by m, by Fermat's little theorem a⁻¹ = am−2 mod m.
#include <iostream>
using namespace std;
const long long MOD = 1000000007;
long long power(long long a, long long b) { // a^b mod MOD
long long r = 1;
a %= MOD;
while (b > 0) {
if (b & 1) r = r * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return r;
}
long long inverse(long long a) { return power(a, MOD - 2); }
int main() {
long long a, b;
cin >> a >> b;
cout << (a + b) % MOD << "\n";
cout << ((a - b) % MOD + MOD) % MOD << "\n"; // never negative
cout << a % MOD * (b % MOD) % MOD << "\n";
cout << a % MOD * inverse(b) % MOD << "\n"; // "a / b" modulo
return 0;
}
For a = 10, b = 4 the last line gives 500000006 – that is the number x for which 4 · x ≡ 10 (mod 109+7), that is, "10/4 = 2.5" modulo.
Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.
TASK 01Difficulty: easy
The day of the week
Today is the day with the order number d (0 = Monday, …, 6 = Sunday). Which day will it be after k days? k can also be negative (how many days ago), |k| ≤ 1018. Print the order number of the day.
Example 1
Input
0 10
Output
3
Example 2
Input
2 -9
Output
0
Hint
The result is (d + k) mod 7, but in C++ the remainder of a negative number is negative – use ((x % 7) + 7) % 7.
Solution (C++)
#include <iostream>
using namespace std;
int main() {
long long d, k;
cin >> d >> k;
long long x = (d + k % 7) % 7;
cout << (x + 7) % 7 << endl; // the mathematical remainder (always 0..6)
return 0;
}
TASK 02Difficulty: medium-hard
The number of divisors
Read a natural number n (n ≤ 1012) and print how many divisors it has.
Example 1
Input
12
Output
6
Example 2
Input
1000000000000
Output
169
Hint
Factorise n into primes by dividing up to √n. If n = p₁^a₁ · … · pₖ^aₖ, the number of divisors is (a₁+1)·…·(aₖ+1). Whatever remains after the loop (if it is greater than 1) is a prime factor with the exponent 1.
Solution (C++)
#include <iostream>
using namespace std;
int main() {
long long n;
cin >> n;
long long divisors = 1;
for (long long p = 2; p * p <= n; p++) {
int a = 0;
while (n % p == 0) { // how many times p divides n
n /= p;
a++;
}
divisors *= (a + 1);
}
if (n > 1) divisors *= 2; // one prime factor has remained
cout << divisors << endl;
return 0;
}
TASK 03Difficulty: harder
A sum of fractions modulo
Calculate 1/1 + 1/2 + … + 1/n modulo 109+7 (n ≤ 106), that is, print Σ i⁻¹ mod p.
Example 1
Input
1
Output
1
Example 2
Input
3
Output
833333341
Hint
Every term is the modular inverse of the number i: ip−2 mod p. For n up to 106 that is about 30 million multiplications – fast enough.
Solution (C++)
#include <iostream>
using namespace std;
const long long MOD = 1000000007;
long long power(long long a, long long b) {
long long r = 1;
a %= MOD;
while (b > 0) {
if (b & 1) r = r * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return r;
}
int main() {
int n;
cin >> n;
long long sum = 0;
for (int i = 1; i <= n; i++)
sum = (sum + power(i, MOD - 2)) % MOD; // 1/i modulo
cout << sum << endl;
return 0;
}
Common mistakes and tips
Always take the remainder after a multiplication; otherwise even a long long overflows.
Fix a negative remainder with ((x % m) + m) % m.
The inverse through Fermat's theorem works only for a prime modulus.
The loop "up to √n" is written as p * p <= n (without sqrt and rounding errors).
Check your knowledge
Open the quiz
Mini quiz: number theory
1. What is -7 % 3 in C++?
2. How many divisors does the number 36 = 2² · 3² have?
3. When is the inverse a⁻¹ = a^(m−2) mod m correct?
Podešavanja kolačića
Koristimo kolačiće da bismo vam pružili najbolje moguće iskustvo. Takođe nam omogućavaju da analiziramo ponašanje korisnika kako bismo stalno poboljšavali veb lokaciju za vas.