Multiple Transform
約数幇助と呼ばれる. 参考 - 高速ゼータ変換の約数版
Spec
i
について, i
を約数に持つj
(上位集合)のa[j]
の総和を求める. \( O(N \log{\log N}) \).
inverse multiple transform
と共に使うとgcd
に関する畳み込みができる. こんな感じ
\[ h(z) = \sum_{\gcd(x, y) = z} {f(x) * g(y)} \]
Code
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
template <class T>
void multiple_transform(vector<T> &a) {
int n = a.size();
vector<bool> sieve(n, true);
for (int p = 2; p < n; ++p) {
if (sieve[p]) {
for (int k = (n - 1) / p; k != 0; --k) {
sieve[k * p] = false;
a[k] += a[k * p];
}
}
}
for (int i = 0; ++i != n;) {
a[i] += a[0];
}
}
template <class T>
void inverse_multiple_transform(vector<T> &a) {
int n = a.size();
vector<bool> sieve(n, true);
for (int i = 0; ++i != n;) {
a[i] -= a[0];
}
for (int p = 2; p < n; ++p) {
if (sieve[p]) {
for (int k = 1; k * p < n; ++k) {
sieve[k * p] = false;
a[k] -= a[k * p];
}
}
}
}