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];
			}
		}
	}
}