Struct cp_library_rs::number_theory::factorize_query::FactorTable

pub struct FactorTable {
    pub n: usize,
    pub sieve: Vec<usize>,
}

前計算ありの素因数分解

Fields

n: usize

sieve: Vec<usize>

Implementations

impl FactorTable

pub fn new(n: usize) -> Self

前計算を行う

• $O(N \log\log N)$ 時間で篩を作成

pub fn factorize(&self, x: usize) -> Vec<usize>

素因数分解を行い，素因数のベクタを返す

戻り値

• 素因数のリスト

• 時間計算量: $O(\log x)$

pub fn factorize_pairs(&self, x: usize) -> Vec<(usize, usize)>

素因数分解を行い，(素因数, 指数) のベクタを返す

戻り値

• (素因数, 指数) のベクタ

• 時間計算量: $O(\log x)$