haar_lib/math/convolution/
conv_gcd.rs

1//! GCD畳み込み
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/// $\mathtt{a_{\gcd (i, j)}} = \sum \mathtt{f_{i}} * \mathtt{g_{j}}$を満たす`a`を求める。
9pub fn convolution_gcd<T>(mut f: Vec<T>, mut g: Vec<T>) -> Vec<T>
10where
11    T: Copy + Add<Output = T> + Sub<Output = T> + Mul<Output = T>,
12{
13    assert_eq!(f.len(), g.len());
14
15    mul_zeta(&mut f);
16    mul_zeta(&mut g);
17
18    for (x, y) in f.iter_mut().zip(g.into_iter()) {
19        *x = *x * y;
20    }
21
22    mul_mobius(&mut f);
23    f
24}