cpp_src/number_theory/Brute.hpp

• View this file on GitHub
• Last update: 2022-03-17 13:38:21+09:00
• Include: #include "cpp_src/number_theory/Brute.hpp"

Code

// O(sqrt(x))
ll totient(ll x) {
    ll res = x;
    for (ll i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            res = res / i * (i - 1);
            while (x % i == 0) {
                x /= i;
            }
        }
    }
    if (x != 1) {
        res = res / x * (x - 1);
    }
    return res;
}

// O(sqrt(x))
bool is_prime(ll x) {
    if (x <= 1) return false;
    for (ll i = 2; i * i <= x; ++i) {
        if (x % i == 0) return false;
    }
    return true;
}

// p:prime
// ord p of n!
ll ord_fac(ll n, ll p) {
    ll res = 0;
    while (n) {
        n /= p;
        res += n;
    }
    return res;
}

#line 1 "cpp_src/number_theory/Brute.hpp"
// O(sqrt(x))
ll totient(ll x) {
    ll res = x;
    for (ll i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            res = res / i * (i - 1);
            while (x % i == 0) {
                x /= i;
            }
        }
    }
    if (x != 1) {
        res = res / x * (x - 1);
    }
    return res;
}

// O(sqrt(x))
bool is_prime(ll x) {
    if (x <= 1) return false;
    for (ll i = 2; i * i <= x; ++i) {
        if (x % i == 0) return false;
    }
    return true;
}

// p:prime
// ord p of n!
ll ord_fac(ll n, ll p) {
    ll res = 0;
    while (n) {
        n /= p;
        res += n;
    }
    return res;
}

Back to top page