haar_lib/math/convolution/
conv_lcm.rs

1//! LCM畳み込み
2use crate::math::convolution::div_mul_transform::*;
3use std::ops::{Add, Mul, Sub};
4
5/// $\mathtt{a_{\mathtt{lcm} (i, j)}} = \sum \mathtt{f_{i}} * \mathtt{g_{j}}$を満たす`a`を求める。
6///
7/// `a`の長さは`|f| = |g|`と等しい。
8pub fn convolution_lcm<T>(mut f: Vec<T>, mut g: Vec<T>) -> Vec<T>
9where
10    T: Copy + Add<Output = T> + Sub<Output = T> + Mul<Output = T>,
11{
12    assert_eq!(f.len(), g.len());
13
14    div_zeta(&mut f);
15    div_zeta(&mut g);
16
17    for (x, y) in f.iter_mut().zip(g.into_iter()) {
18        *x = *x * y;
19    }
20
21    div_mobius(&mut f);
22    f
23}