cp_library_rs/number_theory/
factorize_query.rs

1//! ## 前計算ありの素因数分解
2//!
3//! $`N`$ までの数の素因数分解を
4//! - 前計算: $`O(N \log\log N)`$ 時間
5//! - クエリ: $`O(\log N)`$ 時間
6//!
7//! で行う。
8
9/// 前計算ありの素因数分解
10pub struct FactorTable {
11    pub n: usize,
12    pub sieve: Vec<usize>,
13}
14
15impl FactorTable {
16    /// 前計算を行う
17    /// - $`O(N \log\log N)`$ 時間で篩を作成
18    pub fn new(n: usize) -> Self {
19        let mut sieve = vec![0; n + 1];
20        if n >= 1 {
21            sieve[1] = 1;
22        }
23        for i in 2..=n {
24            if sieve[i] == 0 {
25                // i は素数
26                sieve[i] = i;
27                // i*i から始める（溢れ注意）
28                if i <= n / i {
29                    let mut j = i * i;
30                    while j <= n {
31                        if sieve[j] == 0 {
32                            sieve[j] = i;
33                        }
34                        j += i;
35                    }
36                }
37            }
38        }
39        Self { n, sieve }
40    }
41
42    /// 素因数分解を行い，素因数のベクタを返す
43    ///
44    /// **戻り値**
45    /// - 素因数のリスト
46    ///
47    /// - 時間計算量: $`O(\log x)`$
48    pub fn factorize(&self, mut x: usize) -> Vec<usize> {
49        assert!(1 <= x && x <= self.n);
50        let mut factors = vec![];
51        while x > 1 {
52            let p = self.sieve[x];
53            factors.push(p);
54            x /= p;
55        }
56        factors
57    }
58
59    /// 素因数分解を行い，(素因数, 指数) のベクタを返す
60    ///
61    /// **戻り値**
62    /// - (素因数, 指数) のベクタ
63    ///
64    /// - 時間計算量: $`O(\log x)`$
65    pub fn factorize_pairs(&self, mut x: usize) -> Vec<(usize, usize)> {
66        assert!(1 <= x && x <= self.n);
67        let mut pairs: Vec<(usize, usize)> = vec![];
68        while x > 1 {
69            let p = self.sieve[x];
70            let mut e = 0;
71            while x % p == 0 {
72                x /= p;
73                e += 1;
74            }
75            pairs.push((p, e));
76        }
77        pairs
78    }
79}
cp_library_rs/number_theory/factorize_query.rs

cp_library_rs/number_theory/
factorize_query.rs
