Dirichlet卷积逆

Question

如果是f,g\colon \mathbb{Z}_{\geq 1} \to \mathbb{R}，则定义了f和g的Dirichlet卷积

\qquad\qquad\qquad \displaystyle (f*g)(n) = \sum_{d|n}f(d)g(n/d).

这个问题询问如何计算函数的Dirchlet卷积。Dirichlet卷积的恒等元是函数。

\qquad\qquad\qquad\qquad\,\, e(n)=\begin{cases}1 & n=1 \\ 0 & \text{else}\end{cases}。

如果f*g=e，则f和g是卷积逆。如果f(1)\neq 0，则f有一个卷积逆。有一个反式：

\qquad \qquad \qquad \qquad\,\,\,\displaystyle g(1)=\frac{1}{f(1)}

\qquad \qquad \qquad\qquad\,\, \displaystyle g(n)=\frac{-1}{f(1)}\sum_{\substack{d|n\\d1$}。

任务：

给出一个整数的列表l，计算l的卷积逆。输出应该是与l相同长度的列表。列表l表示函数

\qquad\qquad\qquad\qquad\,\, f(n) = \begin{cases} \text{The $n$th entry of l} & n < \text{len(l)} \\ 0 & \text{else} \end{cases}我的测试用例是一个索引，因为它在上下文中是有意义的。如果您希望在开始时使用忽略的元素填充输入和输出，或者进行其他一些修改以支持零索引，那就好了。大多数其他i/o格式可能是可以接受的。您可以假设输出是整数。

测试用例

Input:  [1, 0, 0, 0, 0, 0, 0]
Output: [1, 0, 0, 0, 0, 0, 0]

Input:  [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Output: [1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0, -1, 1, 1, 0, -1, 0, -1, 0]

Input:  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
Output: [1, -2, -3, 0, -5, 6, -7, 0, 0, 10, -11, 0, -13, 14, 15, 0]

Input:  [1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5]
Output: [1, -2, -2, 1, -2, 4, -2, 0, 1, 4, -2, -2, -2, 4, 4, 0]

Input:  [1, 3, 4, 7, 6, 12, 8, 15, 13, 18, 12, 28, 14, 24, 24, 31, 18, 39]
Output: [1, -3, -4, 2, -6, 12, -8, 0, 3, 18, -12, -8, -14, 24, 24, 0, -18, -9]

Input:  [1, 5, 10, 21, 26, 50, 50, 85, 91, 130]
Output: [1, -5, -10, 4, -26, 50, -50, 0, 9, 130]

Input:  [-1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1]
Output: [-1, -1, 1, -2, 1, 1, 1, -4, 0, 1, 1, 2, 1, 1, -1, -8, 1, 0, 1]

Answer 1

马蒂尔，32字节

1i1)/Gd"GX@QtZ\3L)/)y7M)*s_G1)/h

在网上试试！或验证所有测试用例.

是如何工作的

1        % Push 1
i        % Take input: f, of size L
1)       % Get its first entry: f(1)
/        % Divide: gives 1/f(1). This is g(1). It will later be expanded into
         % a vector to include g(2), g(3), ... g(L)
G        % Push input again
d        % Consecutuve differences: gives a vector of L-1 numbers
"        % For each: this iterates L-1 times
  G      %   Push input again
  X@Q    %   Push iteration index plus 1: gives 2, 3, ..., L respectively in
         %   each iteration. This is n in the formula for computing g(n)
  t      %   Duplicate
  Z\     %   Divisors of n. Gives a vector with the values of d in the formula
  3L)    %   Remove last. This corresponds to the condition d

Answer 2

木炭，33字节

ＦＬθ⊞υ∕∨‹ι²±ΣＥυ∧∧λ¬﹪ιλקθ÷ιλκ§θ¹Ｉυ

在网上试试！链接是详细的代码版本。0-索引；在输入中，第0元素是一个虚拟元素，而在输出中，它是一个重复元素。解释：

ＦＬθ

循环遍历输入列表的索引。

⊞υ

把结果保存下来。

∕∨...§θ¹

每个学期除以f(1)。

‹ι²

对于第0和第1项，分子只是1。

±ΣＥυ∧∧λ¬﹪ιλקθ÷ιλκ

否则，将其索引是当前索引的因子的项与输入中的适当项相乘，并取负和。

Ｉυ

打印结果。

替代重排，也是33个字节：

Ｉ⊟Ｅθ⊞Ｏυ∕∨‹κ²±ΣＥυ∧∧μ¬﹪κμקθ÷κμλ§θ¹

在网上试试！链接是详细的代码版本。