dsalgo 0.3.10

A package for Datastructures and Algorithms.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

use crate::{
    integer_square_root_with_binary_search_usize::isqrt,
    sieve_of_eratosthenes_enumerate_primes_usize::*,
};

/// n < 10^14, min(k, n - k) < 10^7

pub fn factorize_combination(
    n: usize,
    mut k: usize,
) -> Vec<(usize, usize)> {
    let mut factors = vec![];

    if k > n {
        return factors;
    }

    k = k.min(n - k);

    let lo = n - k + 1;

    let mut v: Vec<_> = (lo..=n).collect();

    for p in enumerate_primes(isqrt(n).max(k) + 1) {
        let mut e = 0;

        for i in ((lo + p - 1) / p * p..=n).step_by(p) {
            while v[i - lo] % p == 0 {
                v[i - lo] /= p;

                e += 1;
            }
        }

        for mut x in (p..=k).step_by(p) {
            while x % p == 0 {
                x /= p;

                e -= 1;
            }
        }

        if e > 0 {
            factors.push((p, e));
        }
    }

    for i in 0..k {
        if v[i] > 1 {
            factors.push((v[i], 1));
        }
    }

    factors.sort();

    factors
}

#[cfg(test)]

mod tests {

    use super::*;

    #[test]

    fn test() {
        let cases = vec![
            ((10, 5), vec![(2, 2), (3, 2), (7, 1)]),
            (
                (1_000_000_010, 5),
                vec![
                    (2, 2),
                    (3, 1),
                    (7, 1),
                    (17, 1),
                    (109, 2),
                    (167, 1),
                    (5882353, 1),
                    (500000003, 1),
                    (1000000007, 1),
                    (1000000009, 1),
                ],
            ),
        ];

        for ((n, k), ans) in cases {
            assert_eq!(factorize_combination(n, k), ans);
        }
    }
}