狄利克雷卷積

一、介紹

狄利克雷卷積是一種數論函數的一種特殊卷積形式，命名來自於德國數學家彼得·戴利克雷。對於兩個數論函數f(n)和g(n)，它們的狄利克雷卷積定義為：

(f * g)(n) = Σd|n f(d)g(n/d)

其中，d是n的正因子。狄利克雷卷積有着廣泛的應用，例如在數論中，可以用來定義歐拉函數、除數函數等常見的數論函數；在組合數學中，可以用來計算多項式間的卷積，從而計算組合數的乘積。

二、性質

狄利克雷卷積具有以下的一些性質：

1. 狄利克雷卷積是交換的，即f * g = g * f。
2. 對於任意正整數n，(f * g)(n)=0當且僅當f(n’)=0或g(n’)=0，其中n’為n的任一因子。
3. 單位函數1與任意函數f卷積的結果仍為f本身，即1 * f = f。
4. 如果f(1)≠0，那麼f與其本身的卷積f * f在n>1的時候恆不為零。

三、應用

1. 求解歐拉函數

歐拉函數是一個關於正整數n的數論函數，表示小於或等於n的正整數中與n互質的數的數目，記為φ(n)。歐拉函數可以使用狄利克雷卷積來定義：

φ(n) = (1 * f)(n)

其中，f(n)表示一個分段函數，在n是合數的情況下，f(n)等於0，在n是質數的情況下，f(n)=n-1。

2. 求解除數函數

除數函數表示一個數的除數個數，記為d(n)。除數函數也可以使用狄利克雷卷積來定義，具體來說，我們需要兩個函數：

d(n)= (1 * f)(n)
g(n)=1

其中，f(n)表示一個分段函數，在n是合數的情況下，f(n)等於0，在n是質數的情況下，f(n)=2。

這樣，d(n) = (f * g)(n)。

3. 求解多項式卷積

多項式卷積是指給定兩個多項式f(x)和g(x)，求解它們的乘積h(x)=f(x)g(x)的過程。這個過程可以使用狄利克雷卷積來實現。

具體來說，我們將f(x)和g(x)中的係數視作數論函數：對於f(x)來說，它的係數函數為f(k)，表示f中次數為k的項的係數；對於g(x)來說，它的係數函數為g(k)，表示g中次數為k的項的係數。這樣，h(x)的係數函數就為(f * g)(k)。

有了h(x)的係數函數，我們就可以把它轉化為多項式的形式，得到多項式卷積的結果。

四、代碼示例

1. 求解歐拉函數

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

const int N = 1e6;

bool isprime[N+5];
int phi[N+5];
vector<int> primes;

void sieve() {
  memset(isprime, true, sizeof(isprime));
  isprime[1] = false;
  for (int i = 2; i  N) break;
      isprime[p*i] = false;
      if (i % p == 0) {
        phi[p*i] = phi[i] * p;
        break;
      } else {
        phi[p*i] = phi[i] * (p-1);
      }
    }
  }
}

int main() {
  sieve();
  for (int i = 1; i <= 20; i++) {
    cout << "phi(" << i << ") = " << phi[i] << endl;
  }
  return 0;
}

2. 求解除數函數

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

const int N = 1e6;

bool isprime[N+5];
int d[N+5];
vector<int> primes;

void sieve() {
  memset(isprime, true, sizeof(isprime));
  isprime[1] = false;
  d[1] = 1;
  for (int i = 2; i  N) break;
        if (i % p == 0) {
          int cnt = 0;
          int x = i;
          while (x % p == 0) {
            cnt++;
            x /= p;
          }
          d[p*i] = d[x] * (cnt+1);
          break;
        } else {
          d[p*i] = d[i] * 2; 
        }
      }
    }
  }
}

int main() {
  sieve();
  for (int i = 1; i <= 20; i++) {
    cout << "d(" << i << ") = " << d[i] << endl;
  }
  return 0;
}

3. 求解多項式卷積

#include <bits/stdc++.h>
using namespace std;
using cd = complex<double>;

const double PI = acos(-1);
const int N = 2e5 + 5;

void fft(vector<cd> &a, bool invert) {
  int n = a.size();
  for (int i = 1, j = 0; i < n; i++) {
    int bit = n >> 1;
    while (j >= bit) {
      j -= bit;
      bit >>= 1;
    }
    j += bit;
    if (i < j) swap(a[i], a[j]);
  }

  for (int len = 2; len <= n; len <<= 1) {
    double ang = 2 * PI / len * (invert ? -1 : 1);
    cd wlen(cos(ang), sin(ang));
    for (int i = 0; i < n; i += len) {
      cd w(1);
      for (int j = 0; j < len/2; j++) {
        cd u = a[i+j], v = w * a[i+j+len/2];
        a[i+j] = u + v;
        a[i+j+len/2] = u - v;
        w *= wlen;
      }
    }
  }

  if (invert) {
    for (int i = 0; i < n; i++) {
      a[i] /= n;
    }
  }
}

vector<int> multiply(vector<int> &a, vector<int> &b) {
  vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
  int n = 1;
  while (n < a.size() + b.size()) {
    n <<= 1;
  }
  fa.resize(n);
  fb.resize(n);

  fft(fa, false);
  fft(fb, false);
  for (int i = 0; i < n; i++) {
    fa[i] *= fb[i];
  }
  fft(fa, true);

  vector<int> ret(n);
  for (int i = 0; i < n; i++) {
    ret[i] = round(fa[i].real());
  }
  while (!ret.empty() && ret.back() == 0) {
    ret.pop_back();
  }
  return ret;
}

void multiply_inplace(vector<int> &a, vector<int> &b) {
  vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
  int n = 1;
  while (n < a.size() + b.size()) {
    n <<= 1;
  }
  fa.resize(n);
  fb.resize(n);

  fft(fa, false);
  fft(fb, false);
  for (int i = 0; i < n; i++) {
    fa[i] *= fb[i];
  }
  fft(fa, true);

  a.resize(n);
  for (int i = 0; i < n; i++) {
    a[i] = round(fa[i].real());
  }
  while (!a.empty() && a.back() == 0) {
    a.pop_back();
  }
}

int main() {
  vector<int> a = {1, 2, 3}, b = {4, 5, 6};
  auto c = multiply(a, b);
  for (auto x : c) {
    cout << x << " ";
  }
  cout << endl;
  multiply_inplace(a, b);
  for (auto x : a) {
    cout << x << " ";
  }
  cout << endl;
  return 0;
}