haar_lib/math/convolution/
conv_gcd_lcm.rs

1//! 添字GCD・LCM畳み込み
2//!
3//! # Problems
4//! - <https://judge.yosupo.jp/problem/gcd_convolution>
5use crate::math::convolution::div_mul_transform::*;
6use std::ops::{Add, Mul, Sub};
7
8/// $h_{\gcd (i, j)} = \sum f_i g_j$を満たす$h$を求める。
9///
10/// # Requirements
11/// `f.len()` = `g.len()`
12pub fn convolution_gcd<T>(mut f: Vec<T>, mut g: Vec<T>) -> Vec<T>
13where
14    T: Copy + Add<Output = T> + Sub<Output = T> + Mul<Output = T>,
15{
16    assert_eq!(f.len(), g.len());
17
18    mul_zeta(&mut f);
19    mul_zeta(&mut g);
20
21    for (x, y) in f.iter_mut().zip(g.into_iter()) {
22        *x = *x * y;
23    }
24
25    mul_mobius(&mut f);
26    f
27}
28
29/// $h_{\mathrm{lcm} (i, j)} = \sum f_i g_j$を満たす$h$を求める。
30///
31/// # Requirements
32/// `f.len()` = `g.len()`
33pub fn convolution_lcm<T>(mut f: Vec<T>, mut g: Vec<T>) -> Vec<T>
34where
35    T: Copy + Add<Output = T> + Sub<Output = T> + Mul<Output = T>,
36{
37    assert_eq!(f.len(), g.len());
38
39    div_zeta(&mut f);
40    div_zeta(&mut g);
41
42    for (x, y) in f.iter_mut().zip(g.into_iter()) {
43        *x = *x * y;
44    }
45
46    div_mobius(&mut f);
47    f
48}
haar_lib/math/convolution/conv_gcd_lcm.rs

haar_lib/math/convolution/
conv_gcd_lcm.rs
