haar_lib/math/
count_coprime.rs

1//! 互いに素な数を数える。
2use crate::math::factorize::trial::factorize;
3
4/// `n`以下の自然数で、`m`と互いに素なものの個数を求める。
5pub fn count_coprime(n: u64, m: u64) -> u64 {
6    let ps = factorize(m);
7    let k = ps.len();
8
9    let mut ret = 0;
10
11    for i in 0..1_usize << k {
12        let mut s = 1;
13
14        for (j, (p, _)) in ps.iter().enumerate() {
15            if i & (1 << j) != 0 {
16                s *= p;
17            }
18        }
19
20        if i.count_ones() % 2 == 1 {
21            ret -= n / s;
22        } else {
23            ret += n / s;
24        }
25    }
26
27    ret
28}
29
30#[cfg(test)]
31mod tests {
32    use super::*;
33    use crate::math::gcd_lcm::GcdLcm;
34
35    #[test]
36    fn test() {
37        let n = 2000;
38        let m = 100;
39
40        let ans = (1..=n).filter(|x| x.gcd(m) == 1).count() as u64;
41
42        assert_eq!(count_coprime(n, m), ans);
43    }
44}
haar_lib/math/count_coprime.rs

haar_lib/math/
count_coprime.rs
