Divisor Transform

約数幇助と呼ばれる. 参考 - 高速ゼータ変換の約数版

Spec

iについて, iの約数であるj(下位集合)についてa[j]の総和を求める. \( O(N \log{\log N}) \).
inverse divisor transformと共に使うとlcmに関する畳み込みができる. こんな感じ

\[ h(z) = \sum_{ \operatorname{lcm} (x, y) = z } { f(x) * g(y) } \]

Code

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

template <class T>
void divisor_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 = 1; k * p < n; ++k) {
				sieve[k * p] = false;
				a[k * p] += a[k];
			}
		}
	}
	for (int i = 0; ++i != n;) {
		a[i] += a[0];
	}
}

template <class T>
void inverse_divisor_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 = (n - 1) / p; k != 0; --k) {
				sieve[k * p] = false;
				a[k * p] -= a[k];
			}
		}
	}
}