Генерация случайных чисел. Теория Гольдбаха. НОД и НОК

4. Генерация случайных чисел

       Для генерации простых чисел нужно следующее

 

#include <random> #include <time.h> ... srand(time(0)); cout << rand() << endl; cout << rand() % MOD;   random_shuffle(permutation.begin(), permutation.end());

       Данный рандом крайне плох тем, что его диапазон всего 32 тысячи, и используется линейный конгруэнтный генератор.

 

#include <random> #include <time.h> #include <chrono> ... mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); mt19937 rng(time(0)); // тоже работает uniform_int_distribution<int> uid(-1000000000, 1000000000); cout << uid(rng) << endl; shuffle(permutation.begin(), permutation.end(), rng);

 

       Данный генератор основан на вихре Мерсенна период которого составляет 219937 − 1

 

       Иногда в олимпиадах блокируется доступ ко времени, тогда в качестве зерна вы можете использовать либо константу, либо адрес указателя

int * x = new int[1]; cout << (int)x;   // генерация случайного простого модуля int getMod() {        uniform_int_distribution<int> u(1e9, 2e9);        int x = u(rng);        while (!isPrime(x))                    ++x;        return x; }   // получение случайного числа для инициализации рандомизатора, при заблокированных функциях времени int getTrueRand() {        int *a = 0;        int rnd = 0;        for (int i = 0; i < 3; ++i) {                    a = new int;                    rnd ^= (int)a;        }        return rnd; }

 

 

5. Теория Гольдбаха

Утверждение о том, что любое чётное число, начиная с 4, можно представить в виде суммы двух простых чисел. Не доказано, но проверено для всех небольших чисел.

Тернарная проблема Гольдбаха, согласно которой любое нечётное число, начиная с 7, можно представить в виде суммы трёх простых чисел была доказана.

 

6. НОД и НОК

       Алгоритм Евклида

Заметим, вначале, что gcd(a,b)=gcd(b,a)

gcd(a, b) = a, if b == 0

       = gcd(b, a - b), b > 0

предполагается, что a > b, иначе поменять местами

Доказательство

       Если g=gcd(a,b) делит и a, и b, то их разность (a−b) тоже будет делиться на g.

       Никакой больший делитель d числа b не может делить число (a−b): если d > g, то d не может делить a, а значит и не делит (a−b).

Сложность данного алгоритма линейная.

 

Ускорим его, заменив a - b на a % b, так как это эквивалентно последовательности вычитаний до момента, когда a станет меньше b. Легко видеть, что если a > b, то после операции a уменьшится хотя бы в 2 раза. За счёт этого алгоритм имеет логарифмическую сложность, а именно O(log min(a,b))

 

Функции обобщаются на множество чисел

gcd(a,b,c,d)=gcd(gcd(gcd(a,b),c),d)

lcm(a,b,c,d)=lcm(lcm(lcm(a,b),c),d)

 

Также полезно знать, что нахождение gcd группы из n чисел от 1 до A будет работать не за O(n log A), а за O(n + log A) — это несложно доказать по индукции.

 

Ещё один интересный факт в том, что НОД чисел Фибоначчи вычисляется в среднем дольше, чем других чисел.

 

Также важно, что НОД двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным наибольшему общему делителю индексов, то есть

 

 

lcm(a, b) = a / gcd(a, b) * b - чтобы избежать переполнения

 

int gcd(int a, int b) { // O(log min(a,b))        if (b == 0)                    return a;        return gcd(b, a % b); } int gcd_no_recursion (int a, int b) {        while (b) {                    a %= b;                    swap(a, b);        }        return a; } int lcm (int a, int b) {        return a / gcd(a, b) * b; }