анти. Guide to Competitive

• Название: Guide to Competitive
• Дата: 20.12.2022
• Размер: 2.39 Mb.
• Имя файла: анти.pdf
• Тип: Guide; #854732
• страница: 13 из 26

Глава
11
Математика
В этой главе речь пойдет о математических методах, регулярно встречаю- щихся в олимпиадном программировании. Мы обсудим теоретические результаты и научимся применять их в алгоритмах.
В разделе 11.1 обсуждаются вопросы теории чисел. Мы узнаем об ал- горитмах нахождения простых множителей числа, об арифметике по мо- дулю и об эффективных способах решения уравнений в целых числах.
В разделе 11.2 изучаются различные подходы к решению комбинатор- ных задач: как эффективно подсчитать допустимые комбинации объек- тов. Среди прочего будут рассмотрены биномиальные коэффициенты, числа Каталана и формула включений-исключений.
В разделе 11.3 показано, как использовать матрицы при программиро- вании алгоритмов. Например, мы узнаем, как ускорить работу алгорит- ма динамического программирования за счет эффективного возведения мат рицы в степень.
В разделе 11.4 сначала обсуждаются простые методы вычисления вероят ностей событий и понятие марковской цепи. После этого рассмат- риваются примеры рандомизированных алгоритмов.
Раздел 11.5 посвящен теории игр. Сначала мы изучим оптимальную стратегию простой игры в палочки, основанную на теории игры ним, а затем обобщим эту стратегию на широкий круг других игр.
11.1. Теория чисел
Теория чисел – это область математики, в которой изучаются целые числа.
В этом разделе мы обсудим избранные вопросы и алгоритмы теории чи- сел, в т. ч. нахождение простых чисел, разложение на простые множители и решение уравнений в целых числах.
11.1.1. Простые числа и разложение на простые
множители
Целое число a называется множителем, или делителем целого числа b, если a делит b. Если a – множитель b, то мы пишем a | b, иначе a  b. Напри- мер, множителями числа 24 являются 1, 2, 3, 4, 6, 8, 12 и 24.

11.1. Теория чисел

173
Целое число n > 1 называется простым, если его единственными поло- жительными множителями являются 1 и n. Например, числа 7, 19 и 41 прос- тые, а 35 – не простое (составное), потому что 5 · 7 = 35. Для каждого целого числа n > 1 существует единственное разложение на простые множители:
1 2
1 2
,
k
k
n
p p
p
α
α
α
=

где p
1
, p
2
, …, p
k
– различные простые числа, а α
1
,α
2
, …,α
k
– положительные целые числа. Например, число 84 разлагается на простые множители сле- дующим образом:
84 = 2 2
· 3 1
· 7 1
.
Обозначим τ(n) количество простых множителей целого числа n. Напри- мер, τ(12)= 6, поскольку множителями 12 являются 1, 2, 3, 4, 6 и 12. Вычис- лить τ(n) можно по формуле
1
( )
(
1),
k
i
i
n
=
τ
=
α +
∏
потому что для каждого простого p
i
существует α
i
+ 1 способов выбрать, сколько раз оно входит в множитель. Например, 12 = 2 2
· 3, поэтому
τ(12)= 3 · 2 = 6.
Обозначим σ(n) сумму всех множителей числа n. Например, σ(12)= 28, т. к. 1 + 2 + 3 + 4 + 6 + 12 = 28. Значение σ(n) вычисляется по формуле
1 1
1 1
( )
(1
)
,
1
i
i
k
k
i
i
i
i
i
i
p
n
p
p
p
α +
α
=
=
−
σ
=
+
+ +
=
−
∏
∏

следующей из формулы суммы геометрической прогрессии. Например,
σ(12) = (2 3
− 1)/(2 − 1) · (3 2
− 1)/(3 − 1) = 28.
Основные алгоритмы. Если целое число n не простое, то его можно представить в виде произведения a · b, где a ≤ √n или b ≤ √n, поэтому среди его множителей обязательно имеется число от 2 до ⌊√n⌋. Следовательно, проверить простоту числа и найти его разложение на простые множители можно за время O(√n).
Показанная ниже функция prime проверяет, является ли целое число n
простым. Она пытается поделить n на все целые числа от 2 до ⌊√n⌋; если ни одно из них не является делителем, то n простое.
bool prime(int n) {
if (n < 2) return false;
for (int x = 2; x*x <= n; x++) {
if (n%x == 0) return false;
}

174 
Глава 11. Математика
return true;
}
Следующая функция строит вектор, содержащий разложение n на прос- тые множители. Функция делит число n на его простые множители и до- бавляет их в вектор. Процесс заканчивается, когда у n не останется множи- телей между 2 и ⌊√n⌋. Если при этом n > 1, то оно простое и добавляется в качестве последнего множителя.
vector<int> factors(int n) {
vector<int> f;
for (int x = 2; x*x <= n; x++) {
while (n%x == 0) {
f.push_back(x);
n /= x;
}
}
if (n > 1) f.push_back(n);
return f;
}
Отметим, что каждый простой множитель встречается в этом векторе столько раз, какова его степень в разложении n. Например, 12 = 2 2
· 3, по- этому функция вернет результат [2, 2, 3].
Свойства простых чисел. Легко доказать, что простых чисел бесконеч- но много. Если бы это было не так, то мы могли бы построить множество
P = {p
1
, p
2
, …, p
n
}, содержащее все простые числа. В него вошли бы p
1
= 2,
p
2
= 3, p
3
= 5 и т. д. Но тогда рассмотрим число
p
1
p
2
… p
n
+ 1.
Оно больше каждого из элементов P и не делится ни на один из них.
Следовательно, его наименьший простой множитель больше каждого из чисел p
1
, p
2
, …, p
n
в противоречии с тем, что p
n
– наибольшее простое число. Таким образом, множество простых чисел должно быть беско- нечным.
Обозначим π(n)количество простых чисел, не превосходящих n. Напри- мер, π(10) = 4, поскольку существует четыре простых числа, не превосхо- дящих 10: 2, 3, 5 и 7. Можно доказать, что
( )
,
ln
n
n
n
π
≈
т. е. простые числа встречаются довольно часто. Так, приближенное значе- ние π(10 6
) равно 10 6
/ ln 10 6
≈ 72 382, а точное значение равно 78 498.

11.1. Теория чисел

175
11.1.2. Решето Эратосфена
Решето Эратосфена – это алгоритм предварительной обработки, ко- торый строит массив sieve
, позволяющий для каждого целого числа от 2 до n эффективно определить, является ли оно простым. Если x простое, то sieve
[x
] = 0, иначе sieve
[x
] = 1. На рис. 11.1 показано содержимое массива sieve для n = 20.
0 0
1 0
1 0
1 1
1 0
1 0
1 1
1 0
1 0
1 2
3 4
5 6
7 8
9 10 11 12 13 14 15 16 17 18 19 20
Рис. 11.1. Результат работы решета Эратосфена для n = 20
Для построения массива алгоритм перебирает числа 2 · n. Обнаружив новое простое число x, алгоритм помечает, что числа 2x,3x,4x и т. д. не прос тые. Ниже показана возможная реализация алгоритма в предположе- нии, что вначале все элементы sieve равны нулю:
for (int x = 2; x <= n; x++) {
if (sieve[x]) continue;
for (int u = 2*x; u <= n; u += x) {
sieve[u] = 1;
}
}
Внутренний цикл алгоритма выполняется ⌊n/x⌋ раз для каждого значе- ния x. Следовательно, время работы может быть оценено сверху частич- ной суммой гармонического ряда:
2
/
/ 2
/ 3
/ 4
( log ).
n
x
n x
n
n
n
O n
n
=
=
+
+
+
=

 
 
 


 
 
 

∑

На самом деле алгоритм более эффективен, поскольку внутренний цикл выполняется, только если число x простое. Можно показать, что временная сложность алгоритма равна всего лишь O(n log log n), что весьма близко к
O(n). На практике решето Эратосфена очень эффективно; в табл. 11.1 по- казано реальное время выполнения для различных n.
Таблица 11.1. Время работы решета Эратосфена
Верхняя граница n
Время работы (с)
10 6
0.01 2 · 10 6
0.03 4 · 10 6
0.07 8 · 10 6
0.14

176 
Глава 11. Математика
Верхняя граница n
Время работы (с)
16 · 10 6
0.28 32 · 10 6
0.57 64 · 10 6
1.16 128 · 10 6
2.35
Существует несколько обобщений решета Эратосфена. Например, для каждого числа k можно вычислить его наименьший простой множитель
(рис. 11.2). А после этого мы с помощью решета можем эффективно раз- ложить на множители любое число от 2 до n. (Отметим, что количество простых множителей числа n имеет порядок O(log n).)
2 3
2 5
2 7
2 3
2 11 2
13 2
3 2
17 2
19 2
2 3
4 5
6 7
8 9
10 11 12 13 14 15 16 17 18 19 20
Рис. 11.2. Обобщенное решето Эратосфена для n = 20
11.1.3. Алгоритм Евклида
Наибольшим общим делителем (НОД) целых чисел a и b, gcd(a, b), назы- вается наибольшее целое число, которое делит одновременно a и b. На- пример, gcd(30, 12) = 6. С наибольшим общим делителем тесно связано понятие наименьшего общего кратного (НОК) – наименьшего целого чис- ла, которое делится одновременно на a и на b; оно обозначается lcm(a, b).
Формулу
( , )
gcd( , )
ab
a b
a b
=
lcm можно использовать для вычисления наименьшего общего кратного. На- пример, lcm(30, 12) = 360/gcd(30, 12) = 60.
Один из способов нахождения gcd(a, b) – разложить a и b на простые множители, а затем для каждого простого числа взять наибольшую степень, в которой оно входит в оба разложения. Так, чтобы вычислить gcd(30, 12), мы можем построить разложения 30 = 2 · 3 · 5 и 12 = 2 2
· 3, а затем сделать вывод, что gcd(30, 12) = 2 · 3 = 6. Однако для больших a и b
этот метод неэффективен.
Алгоритм Евклида дает эффективный способ вычисления gcd(a, b). Он основан на формуле
a
b = 0
gcd(a, b) =
�
gcd(b, a mod b)
b ≠ 0

11.1. Теория чисел

177
Например:
gcd(30, 12) = gcd(12, 6) = gcd(6, 0) = 6.
Этот алгоритм можно реализовать следующим образом:
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a%b);
}
Почему данный алгоритм работает? Чтобы разобраться в этом, обра- тимся к рис. 11.3, где x = gcd(a, b). Поскольку число x делит a и b, оно должно делить и a mod b, откуда следует справедливость рекуррентной формулы.
a b
b a
mod b x
x x
x x
x x
x
Рис. 11.3. Почему работает алгоритм Евклида
Можно доказать, что алгоритм Евклида работает за время O(log n), где
n = min(a, b).
Расширенный алгоритм Евклида. Алгоритм Евклида можно модифи- цировать так, чтобы он давал числа x и y – такие, что
ax
+ by = gcd(a, b).
Например, при a = 30 и b = 12 имеем
30 · 1 + 12 · (−2) = 6.
Эту задачу также можно решить, воспользовавшись тождеством gcd(a, b)= gcd(b, a mod b). Предположим, что задача уже решена для gcd(b, a mod b), и мы знаем x' и y' – такие, что
bx' + (a mod b)y' = gcd(a, b).
Тогда поскольку a mod b = a − ⌊a/b⌋ · b, то
bx' + (a − ⌊a/b⌋ · b)y' = gcd(a, b),
или
ay'
+ b(x' − ⌊a/b⌋ · y') = gcd(a, b).
Таким образом, мы можем взять x = y' и y = x' −⌊a/b⌋ · y'. На этой идее осно- вана показанная ниже функция, которая возвращает кортеж (x, y, gcd(a, b)), удовлетворяющий уравнению.

178 
Глава 11. Математика tuple<int,int,int> gcd(int a, int b) {
if (b == 0) {
return {1,0,a};
} else {
int x,y,g;
tie(x,y,g) = gcd(b,a%b);
return {y,x-(a/b)*y,g};
}
}
Эту функцию можно использовать следующим образом:
int x,y,g;
tie(x,y,g) = gcd(30,12);
cout << x << " " << y << " " << g << "\n"; // 1 -2 6
11.1.4. Возведение в степень по модулю
Часто бывает нужно эффективно вычислить значение x
n
mod m. Это можно сделать за время O(log n), воспользовавшись следующим рекур- рентным соотношением:
⎧1
n
= 0
x
n
=
⎨
x
n
/2
· x
n
/2
n
четно .
⎩x
n
−1
· x
x
нечетно
Например, для вычисления x
100
мы сначала вычисляем x
50
, а затем поль- зуемся формулой x
100
= x
50
· x
50
. Далее для вычисления x
50
мы сначала вычис- ляем x
25
и т. д. Поскольку при четном n показатель степень уменьшается вдвое, это вычисление занимает время O(log n).
Алгоритм реализуется следующей функцией:
int modpow(int x, int n, int m) {
if (n == 0) return 1%m;
long long u = modpow(x,n/2,m);
u = (u*u)%m;
if (n%2 == 1) u = (u*x)%m;
return u;
}
11.1.5. Теорема Эйлера
Два целых числа a и b называются взаимно простыми, если gcd(a, b) = 1.
Функция Эйлера φ(n) определяет количество целых чисел от 1 до n, взаим- но простых с n. Например, φ(10) = 4, потому что числа 1, 3, 7 и 9 взаимно просты с 10.

11.1. Теория чисел

179
Для любого n значение φ(n)можно вычислить, зная разложение n на простые множители, по формуле
1 1
( )
(
1).
i
k
i
i
i
n
p
p
α −
=
ϕ
=
−
∏
Например, поскольку 10 = 2 · 5, то φ(10) = 20 · (2 − 1) · 50 · (5 − 1) = 4.
Теорема Эйлера утверждает, что
x
φ(m)
mod m = 1
для всех положительных взаимно простых чисел x и m. Так, согласно тео- реме Эйлера 7 4
mod 10 = 1, поскольку 7 и 10 – взаимно простые числа и
φ(10) = 4.
Если m простое, то φ(m)= m − 1, и эта формула принимает вид
x
m−1
mod m = 1.
В таком виде она известна как малая теорема Ферма. Из нее следует, что
x
n
mod m = x
n
mod (m−1)
mod m,
и этот факт можно использовать для вычисления x
n
при очень больших n.
Вычисление обратной величины по модулю. Обратной величиной x
относительно умножения по модулю m называется такое число inv
m
(x), что
x · inv
m
(x)mod m = 1.
Например, inv
17
(6) = 3, т. к. 6 · 3 mod 17 = 1.
Обращение по модулю позволяет делить числа по модулю m, посколь- ку деление x эквивалентно умножению на inv
m
(x). Например, зная, что inv
17
(6) = 3, мы можем вычислить, чему равно 36/6 mod 17, найдя значение
36 · 3 mod 17.
Обращение по модулю возможно тогда и только тогда, когда x и m взаим- но просты. В этом случае справедлива формула inv
m
(x) = x
φ(m)−1
,
основанная на теореме Эйлера. В частности, если число m простое, то
φ(m)= m – 1, и эта формула принимает вид inv
m
(x) = x
m−2
Например:
inv
17
(6) mod 17 = 6 17−2
mod 17 = 3.
Данная формула позволяет эффективно вычислять обратные величины по модулю, применяя алгоритм возведения в степень по модулю (см. раз- дел 11.1.4).

180 
Глава 11. Математика
11.1.6. Решение уравнений в целых числах
Диофантовы уравнения. Диофантовым уравнением называется урав- нение вида
ax
+ by = c,
где a, b и c – постоянные, а найти требуется x и y. Все числа в этом уравне- нии должны быть целыми. Например, одним из решений уравнения
5x + 2y = 11
является x = 3, y = −2.
Для эффективного решения диофантова уравнения можно воспользо- ваться расширенным алгоритмом Евклида (раздел 11.1.3), который нахо- дит целые числа x и y – такие, что удовлетворяется уравнение
ax
+ by = gcd(a, b).
Диофантово уравнение разрешимо тогда и только тогда, когда c делится на gcd(a, b).
Например, найдем целые x и y, удовлетворяющие уравнению
39
x + 15y = 12.
Это уравнение разрешимо, потому что gcd(39, 15) = 3 и 3 | 12. Расширен- ный алгоритм Евклида дает
39 · 2 + 15 · (−5) = 3,
а после умножения на 4 это равенство принимает вид
39 · 8 + 15 · (−20) = 12,
так что решением уравнения является x = 8, y = −20.
Решение диофантова уравнения не единственно, потому что, зная одно решение, можно получить еще бесконечно много. Если пара (x, y)является решением, то решениями будут и все пары вида
,
( , )
( , )
kb
ka
x
y
a b
a b


+
−




gcd gcd
,
где k – любое целое число.