Теория чисел. Начало

Есть большое количество разных задач и алгоритмов, связанных с простым манипулированием числами. Они происходят из базовых основ арифметики и операций с числами. В данной лекции рассмотрены некоторые математические абстракции и задачи, связанные с анализом чисел.

Но начнём мы с повторения прошлого материала.

In [1]:
#include <iostream>
#include <vector>

using namespace std;

Переполнения и потери точности

In [2]:
{
    int x = 100;
    cout << x*x << endl;
    
    x = 10000;
    cout << x*x << endl;
    
    x = 1000000000;
    cout << x*x << endl;
}
10000
100000000
-1486618624
In [3]:
{
    unsigned long long x = 100;
    cout << x*x << endl;
    
    x = 10000;
    cout << x*x << endl;
    
    x = 1000000000;
    cout << x*x << endl;
}
10000
100000000
1000000000000000000
In [4]:
{
    long double x = 100;
    cout << x*x << endl;
    
    x = 10000;
    cout << x*x << endl;
    
    x = 1000000000;
    cout << x*x << endl;
}
10000
1e+08
1e+18

Логические операторы

In [5]:
{
    bool a = true, b = false;
    cout << ((a && b) ? "true" : "false") << '\n';
}
false
In [6]:
{
    bool a = true, b = false;
    cout << ((a || b) ? "true" : "false") << '\n';
}
true
In [7]:
{
    bool a = true, b = false;
    cout << ((!a) ? "true" : "false") << '\n';
}
false
In [8]:
{
    int a = 5, b = 6;
    if (a > 0 && b++ > 0)
        cout << "a = " << a << " b = " << b;
}
a = 5 b = 7
In [9]:
{
    int a = 5, b = 6;
    if (a > 0 || b++ > 0)
        cout << "a = " << a << " b = " << b;
}
a = 5 b = 6
In [10]:
{
    int a = -5, b = 6;
    if (a > 0 || b++ > 0)
        cout << "a = " << a << " b = " << b;
}
a = -5 b = 7

Векторы

In [11]:
{
    vector<int> a(10, 0);
    
    for (int i = 0; i < 10; i++) {
        a[i] = i;
    }
    
    for (auto a_elem : a) {
        cout << a_elem << " ";
    }    
}
0 1 2 3 4 5 6 7 8 9 

Для хранения массивов данных в C++ есть стандартный контейнер vector. Он может хранить элементы только одного типа, к примеру vector<int>

Сложности алгоритмов

  1. $О(1)$ - константная сложность
  2. $O(\log n)$ - логарифмическая сложность
  3. $O(n)$ - линейная сложность
  4. $O(n\log n)$ - линейно-логарифмическая сложность
  5. $O(n^2)$ - квадратичная сложность
  6. $O(n^3)$ - кубическая сложность
  7. $O(2^n)$ - степенная сложность
  8. $O(n!)$ - факториальная сложность
$N$ Сложность $N = 10$ $N = 100$ $N = 1000$
$n \le 10$ $O(n!)$ 3628800 $9*10^{157}$ $4*10^{2567}$
$n \le 20$ $O(2^n)$ $1024$ $10^{30}$ $10^{301}$
$n \le 500$ $O(n^3)$ $1000$ $1000000$ $1000000000$
$n \le 5000$ $O(n^2)$ $100$ $10000$ $1000000$
$n \le 10^6$ $O(n\log_2n)$ $33$ $664$ $9966$
$n \le 10^9$ $O(n)$ $10$ $100$ $1000$
$n > 10^9$ $O(\log_2 n)$ $3$ $7$ $10$
$n >> 10^9$ $O(1)$ $1$ $1$ $1$

Функции в C++

Чем больше строк кода, тем сложнее понять программу. Для того, чтобы упростить понимание и не писать несколько раз одно и то же, используют функции.

Преимущество функции:

  1. Упрощается текст программы за счет модульности (прочитать и понять несколько вызовов функций легче, чем понять длинную последовательность команд)
  2. Уменьшается дублирование текста
  3. Упрощается отладка и тестирование
  4. Имя функции помогает понять её тело

Рассмотрим, как же писать функции в С++. Объявление функции содержит:

  1. Тип возвращаемого значения (если функция не должна возвращать значение, используется тип *void)*
  2. Имя функции
  3. Параметры функции, которые перечисляются в скобках через запятую
  4. Тело функции реализуется в фигурных скобках. Для возврата значения из функции используется return

Пример (реализуем сумму двух чисел и её вывод):

In [12]:
int Sum (int x, int y) {
    return x + y;
}
In [13]:
void PrintSum(int n, int m) {
    int sum = Sum(n,m);
    cout << "Sum of integers: " << n << " and " << m << " is " << sum;
}
In [36]:
{
    int n, m;
    cin >> n >> m;
    PrintSum(8,16);
}
4 5
Sum of integers: 8 and 16 is 24

Передача параметров по значению

В предыдущем примере параметры функцию передавались по значению. Что это означает? Рассмотрим следующий пример:

In [15]:
void ChangeInteger(int x , int y) {
    x = y;
}
In [41]:
{
    int n, m;
    cin >> n >> m;
    ChangeInteger2(n,m);
    cout << n;
}
3 999
999

Запустив данный код, мы увидим, что выводится число n, а не m, но почему? Оказывается, что значение n копируется в переменную x при вызове функции. Затем мы изменяем значение x, не трогая переменную m.

Передача параметров по ссылке

Хорошо, но как тогда изменить значение n? Всё просто. Следует передать значения по ссылке, а именно:

In [17]:
void ChangeInteger2(int& x , int& y) {
    x = y;
}

Таким образом, для изменения параметров в функции, нужно их передавать по ссылке. Простейший пример, когда нужно изменить параметры по ссылке-это функция swap, которая меняет местами значения:

In [18]:
void Swap(int& x , int& y) {
    int k = x;
    x = y;
    y = k;
}

Передача параметров по константной ссылке

Рассмотрим пример, когда у нас есть вектор из $10^7$ элементов, который мы передаем в функцию, чтобы узнать размер вектора. Мы не будем его изменять и поэтому передадим его по значению.

size_t PrintVectorSize(vector<int> nums) {
        return nums.size();
    }

Если замерить время выполнения этой функции, оно окажется 144 ms. Окей, давайте передадим его по ссылке. Время выполнения будет равным 0 ms. На данный момент у нас появилось уязвимое место в программе, а именно: мы можем случайно изменить вектор, который НЕ ДОЛЖЕН изменяться. От таких случайных изменений существует модификатор const, а именно: нужно передать вектор по константной ссылке. В этом случае вектор не будет копироваться и будет защищен от изменений.

size_t PrintVectorSize(const vector<int>& nums) {
        return nums.size();
    }

Главное значение модификатора const-помочь программисту понять, что данная переменная не должна изменяться. Если попытаться это сделать, компилятор выдаст ошибку.

Кольцо вычетов по модулю $n$

Если два целых числа $a$ и $b$ при деление с остатком на $m$ дают одинаковые остатки, то они называются сравнимыми (или равноостаточными) по модулю числа $m$.

Сравнимость чисел $a$ и $b$ записывается в виде формулы (сравнения):

$ a\equiv b{\pmod {m}} $ Число $m$ называется модулем сравнения.

Определение сравнимости чисел $a$ и $b$ по модулю $m$ равносильно любому из следующих утверждений:

  • разность чисел $a$ и $b$ делится на $m$ без остатка;
  • число $a$ может быть представлено в виде $ a=b+k\cdot m$, где $k$ — некоторое целое число.

Для фиксированного натурального числа $m$ отношение сравнимости по модулю $m$ обладает следующими свойствами:

  • свойством рефлексивности: для любого целого $a$ справедливо $a\equiv a{\pmod {m}}$
  • свойством симметричности: если $a \equiv b \pmod m$, то $ b\equiv a{\pmod {m}};$
  • свойством транзитивности: если $ a\equiv b{\pmod m}$ и $b \equiv c \pmod m$, то $a \equiv c \pmod m$.

Сравнения по одному и тому же модулю обладают многими свойствами обычных равенств. Например, их можно складывать, вычитать и перемножать: если числа $ a_{1},a_{2},\ldots ,a_{n} $ и $b_{1},b_{2},\ldots ,b_{n}$ попарно сравнимы по модулю $m$, то их суммы $a_{1}+a_{2}+\ldots +a_{n}$ и $b_{1}+b_{2}+\ldots +b_{n}$, а также произведения $a_{1}\cdot a_{2}\cdot ...\cdot a_{n}$ и $ b_{1}\cdot b_{2}\cdot ...\cdot b_{n} $ тоже сравнимы по модулю $m$:

  • $ (a_{1}+a_{2}+\ldots +a_{n})\equiv (b_{1}+b_{2}+\ldots +b_{n}){\pmod {m}};$
  • $ (a_{1}\cdot a_{2}\cdot \ldots \cdot a_{n})\equiv (b_{1}\cdot b_{2}\cdot \ldots \cdot b_{n}){\pmod {m}}.$

При этом нельзя выполнять эти операции со сравнениями, если их модули не совпадают.

К обеим частям сравнения можно прибавить одно и то же число $c$:

$ a\equiv b{\pmod {m}}.$

$ (a+c)\equiv (b+c){\pmod {m}}.$

Также можно перенести число из одной части сравнения в другую со сменой знака:

$ a\equiv (b+c){\pmod {m}};$

$(a-c)\equiv b{\pmod {m}}.$

Если числа $a$ и $b$ сравнимы по модулю $m$, то их степени $a^{k}$ и $b^{k}$ тоже сравнимы по модулю $m$ при любом натуральном $k$:

$ a^{k}\equiv b^{k}{\pmod {m}}.$

K любой из частей сравнения можно прибавить целое число, кратное модулю, то есть, если числа $a$ и $b$ сравнимы по модулю некоторого числа $m$, то и $a + t_1$ сравнимо с $b+t_{2}$ по модулю $m$, где $t_{1}$ и $t_{2}$ — произвольные целые числа, кратные $m$:

$ (a+t_{1})\equiv (b+t_{2}){\pmod {m}} $

Также обе части сравнения и модуль можно умножить на одно и то же число, то есть, если числа $a$ и $b$ сравнимы по модулю некоторого целого числа $m$, то и числа $aq$ и $bq$ сравнимы по модулю числа $mq$, где $q$ — целое:

$aq\equiv bq{\pmod {mq}}$

Сравнения, однако, нельзя, вообще говоря, делить друг на друга или на другие числа. Пример: $ 14\equiv 20{\pmod {6}}$, однако, сократив в 2 раза, мы получаем ошибочное сравнение: $7\equiv 10{\pmod {6}}$. Правила сокращения для сравнений следующие.

Можно делить обе части сравнения на число, но только взаимно простое с модулем: если ${ad}\equiv {bd}{\pmod {m}}$ и НОД ${(d,m)=1}$, то $ a\equiv b{\pmod {m}}$ Если, число $d$ не взаимно просто с модулем, как было в примере, указанном выше, то сокращать на $d$ нельзя.

Можно одновременно разделить обе части сравнения и модуль на их общий делитель: если ${ac}\equiv {bc}{\pmod {mc}}$, то $a\equiv b{\pmod {m}}$.

Поиск противоположного числа

Для того, чтобы найти противоположное по знаку число для $a$ в кольце $m$ надо выполнить следующие преобразования:

$(-a)\pmod{m} = (a \pmod{m} + m) \pmod{m}$

In [19]:
int mod(int a, int m) 
{ 
    return (a%m + m) % m; 
}
In [20]:
{
    cout << "-4 mod 5 = " << mod(-4, 5) << endl;
    cout << "-3 mod 5 = " <<  mod(-3, 5) << endl;
    cout << "-2 mod 5 = " <<  mod(-2, 5) << endl;
    cout << "-1 mod 5 = " <<  mod(-1, 5) << endl;
    cout << "0 mod 5 = " <<  mod(0, 5) << endl;
    cout << "1 mod 5 = " <<  mod(1, 5) << endl;
    cout << "2 mod 5 = " <<  mod(2, 5) << endl;
    cout << "3 mod 5 = " <<  mod(3, 5) << endl;
    cout << "4 mod 5 = " <<  mod(4, 5) << endl;
    cout << "5 mod 5 = " <<  mod(5, 5) << endl;
    cout << "6 mod 5 = " <<  mod(6, 5) << endl;
}
-4 mod 5 = 1
-3 mod 5 = 2
-2 mod 5 = 3
-1 mod 5 = 4
0 mod 5 = 0
1 mod 5 = 1
2 mod 5 = 2
3 mod 5 = 3
4 mod 5 = 4
5 mod 5 = 0
6 mod 5 = 1

Поиск обратного числа

Обратное число для $a$ это число $a^{-1}$ такое что:

$a*a^{-1} \equiv 1 \pmod{n}$

При этом такой элемент существует тогда и только тогда, когда НОД $(a,n)=1$

Для его поиска надо воспользоваться расширенным алгоритмом Евклида.

Алгоритм Евклида поиска НОД (GCD) $(a,b)$

image.png

In [21]:
int gcd(int a, int b)
{
  if (b == 0) return a;
  return gcd(b, a % b);
}
In [22]:
cout << gcd(10, 5) << endl;
cout << gcd(11, 5) << endl;
cout << gcd(12, 6) << endl;
cout << gcd(13, 7) << endl;
cout << gcd(12, 4) << endl;
cout << gcd(13, 5) << endl;
cout << gcd(15, 3) << endl;
5
1
6
1
4
1
3

Алгоритм Евклида можно расширить для нахождения по заданным $a$ и $b$ таких целых $x$ и $y$, что $ax + by = d$, где $d$ – наибольший общий делитель $a$ и $b$.

In [23]:
void gcdext (int a, int b, int &d, int &x, int &y)
{
  int s;

  if (b == 0) {
    d = a; x = 1; y = 0;
    return;
  }

  gcdext(b,a % b,d,x,y);

  s = y;
  y = x - (a / b) * y;
  x = s;
}
In [24]:
{
    int a = 4;
    int b = 6;
    int x, y, d;
    gcdext(a, b, d, x, y);
    cout << "x=" << x << " y=" << y << " d=" << d << endl;
    cout << "ax + by = d: " << a*x + b*y << "=" << d;
}
x=-1 y=1 d=2
ax + by = d: 2=2

Для нахождения обратного по модулю элемента требуется выполнить следующие действия:

  1. Использовать расширенный алгоритм Евклида для нахождения $x$ и $y$, таких что $ax + ny = d$, где $d=НОД(a,n)$.
  2. Если $d > 1$, то обратного элемента не существует. Иначе возвращаем $x$.
In [25]:
int inverse(int a, int n) {
  int d, x, y;
  gcdext(a, n, d, x, y);
  if (d == 1) return x;

  return 0;
}
In [26]:
{
    int a = 5, n = 7;
    cout << "a=" << a << " n=" << n << " inv=" << inverse(a, n) << " check: " << ((a * inverse(a, n)) % n) << endl;
}
a=5 n=7 inv=3 check: 1
In [27]:
{
    int a = 2, n = 7;
    cout << "a=" << a << " n=" << n << " inv=" << mod(inverse(a, n), n) << " check: " << (a * mod(inverse(a, n), n) % n) << endl;
}
a=2 n=7 inv=4 check: 1

Как разбивать число на отдельные цифры

Задача: вывести цифры числа в обратном порядке.

In [28]:
{
    int a = (float)rand() / RAND_MAX*100000;
    cout << a << endl;
    for(; a > 0; a = a / 10) {
        cout << a%10 << " ";
    }
}
20126
6 2 1 0 2 

Задачи

Рассмотрим несколько задач.

Задача №1. Сила трёх.

https://leetcode.com/problems/power-of-three/

Требуется определить является ли число $x$ степенью трёх.

Для решения данной задачи требуется лишь делать число на 3 до тех пор, пока остаток от деления на 3 нулевой и число больше 1, если в какой-то момент число перестанет делиться на 3 до того, как станет меньше или равным 1, то оно не делится на 3, иначе делится.

In [29]:
bool isPowerOfThree(int n) {
    while(n > 1) {
        if(n % 3 != 0)
            return false;
        n /= 3;
    }
    return true;
}
In [30]:
{
    cout << "9 is " << (isPowerOfThree(9) ? "power of three" : "no power of three") << endl;
    cout << "27 is " << (isPowerOfThree(27) ? "power of three" : "no power of three") << endl;
    cout << "81 is " << (isPowerOfThree(81) ? "power of three" : "no power of three") << endl;
    cout << "129 is " << (isPowerOfThree(129) ? "power of three" : "no power of three")  << endl;

}
9 is power of three
27 is power of three
81 is power of three
129 is no power of three

Задача №2. X в n-ой степени.

https://leetcode.com/problems/powx-n/

Требуется посчитать $x$ в $n$-ой степени, при этом $n$ может быть меньше $0$.

Есть большое количество способов. Мы рассмотрим бинарное возведение в степень.

In [31]:
double myPow(double x, int n) {
    if(n == 0)
        return 1.0;
    if(n < 0)
        return 1/(x * myPow(x, -(n+ 1)));
    double p = myPow(x, n/2);
    return n & 1 ? p * p * x : p * p;
}
In [32]:
{
    cout << "x =2; n = 5 : " << myPow(2, 5) << endl;
    cout << "x =2; n = -2 : " << myPow(2, -2) << endl;
    cout << "x =2; n = 10 : " << myPow(2, 10) << endl;
}
x =2; n = 5 : 32
x =2; n = -2 : 0.25
x =2; n = 10 : 1024

Задача №3. Завершающие нули факториала

https://leetcode.com/problems/factorial-trailing-zeroes/

Требуется вычислить количество нулей справа в факториале $n!$.

Идея алгоритма лежит в том факте, что у нас каждое число разлагается единственным образом в произведение простых чисел согласно основной теореме арифметики. Завершающие нули образуются когда у нас есть произведения $2$ и $5$ в факториале. Если мы сможем посчитать число наборов $5$ и $2$, которые дают завершающие нули, мы решим задачу. Рассмотрим следующие примеры:

  1. $n=5$: В разложении чисел, входящих в факториал $5!$ есть одна $5$ и три $2$: $2 * 2 * 2 * 3 * 5$. Соотвтетственно, мы имеем лишь одну пару и количество нулей равно одному.
  2. $n=11$: В разложении чисел, входящих в данный факторил два $5$ и восемь $2$: ($2^8 * 3^4 * 5^2 * 7$). Соответственно, там будет два завершающих нуля.

Можно заметить, что количество двоек всегда будет больше количества пятёрок, следовательно нам требуется рассматривать только пятёрки. Для этого надо посчитать сумму от целочисленного деления $n$ на $5, 25, 125, ... $. Сумма этих чисел будет соответствовать количеству пятёрок в разложении. Этим самым мы найдём все возможные комбинации, генерирующие завершающие нули.

In [33]:
int findTrailingZeros(int n) 
{     
    int count = 0; 
  
    for (int i = 5; n / i >= 1; i *= 5) 
        count += n / i; 
  
    return count; 
}
In [34]:
{
    cout << "n = 5 : " << findTrailingZeros(5) << endl; 
    cout << "n = 11 : " << findTrailingZeros(11) << endl; 
    cout << "n = 20 : " << findTrailingZeros(20) << endl; 
}
n = 5 : 1
n = 11 : 2
n = 20 : 4
In [ ]: