kyopro_library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub dyktr06/kyopro_library

:heavy_check_mark: Primitive Root (原子根)
(lib/math/primitive_root.hpp)

Primitive Root (原子根)

概要

素数 $p$ における原子根を $1$ つ求めます。

計算量

Depends on

Verified with

Code

#pragma once

/**
 * @brief Primitive Root (原子根)
 * @docs docs/math/primitive_root.md
 */

#include "../math/rho.hpp"
#include "../others/random.hpp"

long long primitiveRoot(long long p){
    auto modpow = [](__int128_t x, long long n, const long long &m){
        __int128_t ret = 1 % m;
        x %= m;
        while(n > 0){
            if(n & 1) (ret *= x) %= m;
            (x *= x) %= m;
            n >>= 1;
        }
        return ret;
    };

    RandomNumber rnd(1, p - 1);
    vector<unsigned long long> f = Rho::factorize(p - 1);
    while(true){
        long long a = rnd.get();
        bool is_ok = true;
        for(auto x : f){
            if(modpow(a, (p - 1) / x, p) == 1){
                is_ok = false;
                break;
            }
        }
        if(is_ok){
            return a;
        }
    }
}
#line 2 "lib/math/primitive_root.hpp"

/**
 * @brief Primitive Root (原子根)
 * @docs docs/math/primitive_root.md
 */

#line 2 "lib/math/rho.hpp"

/**
 * @brief Pollard's Rho
 * @docs docs/math/rho.md
 */

namespace Rho{
    unsigned long long mul(unsigned long long a, unsigned long long b, const unsigned long long mod) {
        long long ret = a * b - mod * (unsigned long long)(1.0L / mod * a * b);
        return ret + mod * (ret < 0) - mod * (ret >= (long long) mod);
    }

    bool rabin_miller(unsigned long long n){
        switch(n){
        case 0: // fall-through
        case 1: return false;
        case 2: return true;
        }

        if(n % 2 == 0) return false;
        vector<long long> A = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
        unsigned long long s = 0, d = n - 1;
        while(d % 2 == 0){
            s++;
            d >>= 1;
        }

        auto modpow = [](unsigned long long x, unsigned long long e, const unsigned long long mod) -> unsigned long long {
            unsigned long long ret = 1 % mod;
            x %= mod;
            while(e > 0){
                if(e & 1) ret = mul(ret, x, mod);
                x = mul(x, x, mod);
                e >>= 1;
            }
            return ret;
        };

        for(auto a : A){
            if(a % n == 0) return true;
            unsigned long long t, x = modpow(a, d, n);
            if(x != 1){
                for(t = 0; t < s; ++t){
                    if(x == n - 1) break;
                    x = mul(x, x, n);
                }
                if(t == s) return false;
            }
        }
        return true;
    }

    mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
    unsigned long long FindFactor(unsigned long long n) {
        if(n == 1 || rabin_miller(n)) return n;
        if(n % 2 == 0) return 2;
        unsigned long long c = 1, x = 0, y = 0, t = 0, prod = 2, x0 = 1, q;
        auto f = [&](unsigned long long X) { return mul(X, X, n) + c;};

        while(t++ % 128 or __gcd(prod, n) == 1) {
            if(x == y) c = rng() % (n - 1) + 1, x = x0, y = f(x);
            if((q = mul(prod, max(x, y) - min(x, y), n))) prod = q;
            x = f(x), y = f(f(y));
        }
        return __gcd(prod, n);
    }

    vector<unsigned long long> factorize(unsigned long long x) {
        if(x == 1) return {};
        unsigned long long a = FindFactor(x), b = x / a;
        if(a == x) return {a};
        vector<unsigned long long> L = factorize(a), R = factorize(b);
        L.insert(L.end(), R.begin(), R.end());
        return L;
    }

    vector<unsigned long long> divisor(unsigned long long x){
        vector<unsigned long long> factor = Rho::factorize(x);
        map<unsigned long long, int> countFactor;
        for(auto x : factor){
            if(countFactor.count(x) == 0) countFactor[x] = 0;
            countFactor[x]++;
        }
        vector<unsigned long long> ret = {1};
        for(auto [x, cnt] : countFactor){
            int n = ret.size();
            for(int i = 0; i < n; ++i){
                unsigned long long z = ret[i];
                for(int j = 0; j < cnt; ++j){
                    z *= x;
                    ret.push_back(z);
                }
            }
        }
        return ret;
    }
}
#line 2 "lib/others/random.hpp"

/**
 * @brief Random (乱数生成)
 * @docs docs/others/random.md
 */

struct RandomNumber{
    int64_t seed = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count();
    uniform_int_distribution<long long> p;
    mt19937_64 rnd;

    RandomNumber(long long l = 0, long long r = 0){
        rnd = mt19937_64(seed);
        p = uniform_int_distribution<long long>(l, r);
    }

    long long get(){
        return p(rnd);
    }
};
#line 10 "lib/math/primitive_root.hpp"

long long primitiveRoot(long long p){
    auto modpow = [](__int128_t x, long long n, const long long &m){
        __int128_t ret = 1 % m;
        x %= m;
        while(n > 0){
            if(n & 1) (ret *= x) %= m;
            (x *= x) %= m;
            n >>= 1;
        }
        return ret;
    };

    RandomNumber rnd(1, p - 1);
    vector<unsigned long long> f = Rho::factorize(p - 1);
    while(true){
        long long a = rnd.get();
        bool is_ok = true;
        for(auto x : f){
            if(modpow(a, (p - 1) / x, p) == 1){
                is_ok = false;
                break;
            }
        }
        if(is_ok){
            return a;
        }
    }
}
Back to top page