competitive/math/
prime.rs

1pub fn euler_phi(n: usize) -> usize {
2    let mut n = n;
3    let mut res = n;
4    for i in 2..(n as f32).sqrt() as usize + 1 {
5        if n % i == 0 {
6            res = res / i * (i - 1);
7            while n % i == 0 {
8                n /= i;
9            }
10        }
11    }
12    if n != 1 {
13        res = res / n * (n - 1);
14    }
15    res
16}
17
18#[derive(Clone, Debug)]
19pub struct EulerPhiTable {
20    table: Vec<usize>,
21}
22impl EulerPhiTable {
23    pub fn new(max_n: usize) -> Self {
24        let mut table = (0..max_n + 1).collect::<Vec<_>>();
25        for i in 2..max_n + 1 {
26            if table[i] == i {
27                let mut j = i;
28                while j <= max_n {
29                    table[j] = table[j] / i * (i - 1);
30                    j += i;
31                }
32            }
33        }
34        EulerPhiTable { table }
35    }
36    pub fn get(&self, n: usize) -> usize {
37        self.table[n]
38    }
39}
40
41#[codesnip::entry]
42/// g(d) = Sigma mu(d) * f(n/d)
43pub fn moebius(n: usize) -> std::collections::HashMap<usize, i64> {
44    let mut res = std::collections::HashMap::new();
45    let mut primes = vec![];
46    let mut n = n;
47    for i in 2..(n as f32).sqrt() as usize + 1 {
48        if n % i == 0 {
49            primes.push(i);
50            while n % i == 0 {
51                n /= i;
52            }
53        }
54    }
55    if n != 1 {
56        primes.push(n);
57    }
58    let m = primes.len();
59    for i in 0..1 << m {
60        let (mut mu, mut d) = (1, 1);
61        for (j, p) in primes.iter().enumerate() {
62            if i & (1 << j) != 0 {
63                mu *= -1;
64                d *= p;
65            }
66        }
67        res.insert(d, mu);
68    }
69    res
70}
71
72#[codesnip::entry]
73/// [(hcn, #divisor)]
74pub fn highly_composite_number(n: u128) -> Vec<(u128, u128)> {
75    let mut dp = vec![(1u128, 1u128)];
76    let mut acc = 1u128;
77    let mut table = [false; 110];
78    for p in 2u128.. {
79        if !table[p as usize] {
80            for i in (p..110).step_by(p as _) {
81                table[i as usize] = true;
82            }
83            acc = acc.saturating_mul(p);
84            if acc > n {
85                break;
86            }
87            let m = dp.len();
88            for i in 0..m {
89                let (mut a, b) = dp[i];
90                for j in 2.. {
91                    a = a.saturating_mul(p);
92                    let nb = b.saturating_mul(j);
93                    if a > n {
94                        break;
95                    }
96                    dp.push((a, nb));
97                }
98            }
99            dp.sort_unstable();
100            let mut ndp = vec![];
101            let mut mx = 0u128;
102            for (a, b) in dp {
103                if b > mx {
104                    mx = b;
105                    ndp.push((a, b));
106                }
107            }
108            dp = ndp;
109        }
110    }
111    dp
112}
competitive/math/prime.rs

competitive/math/
prime.rs
