Теория Чисел ~ Сириус 05.06

Основная теорема арифметики

Основная теорема арифметики гласит, что каждое число раскладывается на простые множители, причем единственным образом

Факторизация за O(sqrtN)

Пусть у нас есть число N
Оно представимо в виде N = a * b. Заметим, что одно из чисел a и b <= sqrt(n) (иначе a * b > n) => можно перебирать делители N до его корны

Решето Эратосфена за O(NLogLogN)

//БУДЬТЕ АККУРАТНЕЙ С ПЕРЕПОЛНЕНИЕМ!!!
int n;
vector<bool> isPrime(n);
for(int i = 2; i <= n; i++){
    isPrime[i] = true;
}
for(int i = 2; i * i <= n; i++){
    if(isPrime[i]){
        for(int j = i * i; j <= n; j++){
            isPrime[j] = false;
        }
    }
}

Прикол с minDiv (чтобы факторизацию делать)

int n;
vector<int> minDiv(n);
vector<bool> isPrime(n);
for(int i = 2; i <= n; i++){
    isPrime[i] = true;
    minDiv[i] = i;
}
for(int i = 2; i * i <= n; i++){
    if(isPrime[i]){
        for(int j = i * i; j <= n; j++){
            isPrime[j] = false;
            minDiv[j] = min(minDiv[j], i);
        }
    }
}

Диофантовы уравнения

Уравнения вида a*x + b*y = c (a, b, c - известны)

Прикол:
Если (a, b) = g, то существуют x и y такие, что a*x + b*y = g
(a, b) -> (b, a % b)
b * x1 + (a % b) * y1 = g
(Для тех, кто не знал - a % b = a - [a / b] * b)
b*x1 + (a - [a / b] * b) * y1 = a * y1 + b * (x1 - [a / b] * y1)
Пример шапки функции:

int gcd(int a, int b, int &x, int &y){
    ...
}

Заметим, что a * (x + b) + b (y - a) = a * x + b * y => x = x0 + t * b/g;
y = y0 - t * a/g

Теперь решим основную задачу
Воспользуемся тем, что мы умеем решать для НОДа и тупо домножим коэффициенты.
Если c % g == 0 => решений бесконечно много
Если c % g != 0 => решений нет

Функция Эйлера

ф(n) (да, это фи) - количество взаимнопростых чисел, которые меньше n
ф(10) = 4

Заметим тупые свойства:

ф(р) = р - 1
ф(р^n) = p^n - p^(n - 1)

Так же интересное свойство:
ф(a) * ф(b) = ф(a*b) для (a, b) = 1 (я не собираюсь это доказывать, так как а) это никому не нужно, б) это долго и скучно)

Тогда достаточно просто считается ф(n) для любого n
ф(n) = ф(p1^L1 * p2^L2 * p3^L3 * ... ) = ф(p1^L1) * ф(p2^L2) * ... = (тупое свойство 2) = n * (p1 - 1 / p1) * ... * (pK - 1 / pK)
(лучше считать через ans / p, ans *= (p - 1)

int n;
int ans = n;
for(int i = 2; i * i <= n; i++){
    if(n % i == 0){
        ans /= i;
        ans *= (i - 1);
        while(n % i == 0){
            n /= i;
        }
    }
}
if(n > 1){
    ans /= n;
    ans *= (n - 1);
}

Количество делителей числа

Пусть у нас n = p1^L1 + p2^L2 + p3^L3 + ... + pK^LK
Тогда, кол-во делителей = (L1 + 1) * (L2 + 2) * (L3 + 3) * ... * (LK + 1) (очевидно)

Малая Теорема Ферма

a^(p - 1) ≡ 1 (mod p) при (a, p) = 1

Теорема Эйлера

a^ф(n) ≡ 1 (mod m) при (a, m) = 1

Функции модульной арифметики

const int MOD = 998244353;


int add(int a, int b){
    if(a + b >= MOD){
        return a + b - MOD;
    }
    else{
        return a + b;
    }
}


int sub(int a, int b){
    if(a - b < 0){
        return a + b - MOD;
    }
    else{
        return a - b;
    }
}

Китайская теорема об остатках

TODO (сори, я не успел записать)

Мем с модулями

a * g ≡ b * g (mod m * g) -> a ≡ b (mod m)
a * g ≡ b * g (mod m) -> a ≡ b (mod m) при (m, g) = 1
a ≡ b (mod m) -> a + x ≡ b + x (mod m)

С из N по K

(n, k) = n! / (k! * (n - k)!)
n! = (n - 1)! * n

надеюсь я с комментариями нигде не напутал...

int n;
int f[n], rf[n];
for(int i = 1; i < n; i++){
    f[i] = mul(f[i - 1], i); //умножение чисел по модулю
}
rf[n - 1] = inv(f[n - 1]); //обратное число по модулю
for(int i = n - 2; i >= 0; i--){
    rf[i] = mul(rf[i + 1], i + 1); //умножение чисел по модулю
}

Мемы:
1/n = (n - 1)! / n!
N^-1 = f[N - 1] * rf[N] (mod M)

Задачка

Надо найти все простые числа на отрезке [L, R]
(R-L+1 < 1e7)

int l, r;
vector<int> primes; //предпосчитать
vector<bool> isPrime(r - l + 1, true);
for(auto &i : primes){
    for(int j = i * max((l + i - 1) / i, i); j <= r; j += i){
        isPrime[j - l] = false;
    }
}

Линейное решето Эратосфена

int n;
vector<int> minDiv(n);
vector<int> primes;
iota(minDiv.begin(), minDiv.end(), 0);
for(int i = 2; i < n; i++){
    if(minDiv[i] == i){
        primes.pb(i);
    }
    for(auto &p : primes){
        if(p > minDiv[i] || p * i >= n){
            break;
        }
        minDiv[p * i] = p;
    }
}