Lcm Convolution
(Convolution/LCM_Convolution.py)

• View this file on GitHub
• Last update: 2021-08-29 23:22:42+09:00

Outline

数列 $A=(A_i){1 \leq i}, B=(B_j){1 \leq j}$ に対し, $A,B$ の Lcm Convolution $A \oplus B$ を

\[A \oplus B:=\left(\sum_{\substack{1 \leq i,j \\ \operatorname{lcm}(i,j)=k}} A_i B_j \right)_{1 \leq k}\]

と定義する.

Remark

実装において, 長さが $N$ の数列を使いたい場合, プログラム言語の仕様上, 初項が第 $0$ 項になるため, 長さ $(N+1)$ のリストを入力しなければならない.

ただし, 第 $0$ 項は無視して計算される.

また, Gcd Convolution と違い, $1 \leq i \leq N, 1 \leq j \leq M$ のとき, $\operatorname{lcm}(i,j)$ が最大で $NM$ 程度になるので, $L$ で長さの指定をしなければならない.

Verified with

• test_verify/yosupo_library_checker/Convolution/Lcm_Convolution.test.py

Code

def Divisor_Zeta_Transform(A):
    """ A の約数を走る Zeta 変換を行う.

    ※ A[0] の値は無視される.
    """

    N=len(A)-1
    S=[1]*(N+1)

    for p in range(2,N+1):
        if S[p]:
            for k in range(1,N//p+1):
                S[k*p]=0
                A[k*p]+=A[k]

    for i in range(1,N+1):
        A[i]%=Mod

def Divisor_Mobius_Transform(A):
    """ A の約数を走るにおける Mobius 変換を行う.

    ※ A[0] の値は無視される.
    """

    N=len(A)-1
    S=[1]*(N+1)

    for p in range(2,N+1):
        if S[p]:
            for k in range(N//p,0,-1):
                S[k*p]=0
                A[k*p]-=A[k]

    for i in range(1,N+1):
        A[i]%=Mod

def Convolution_LCM(A,B,L=None):
    """ A,B の lcm における畳み込みを行う.

    L: 結果の長さの最大値 (一般的に, lcm(n,m)<=nm なため)
    ※ A[0], B[0] の値は無視される.
    """

    N=len(A)-1; M=len(B)-1; K=max(N,M)
    if L==None:
        L=K*(K-1)

    A=A+[0]*(L-N)
    B=B+[0]*(L-M)

    Divisor_Zeta_Transform(A)
    Divisor_Zeta_Transform(B)

    for i in range(1,L+1):
        A[i]*=B[i]
        A[i]%=Mod

    Divisor_Mobius_Transform(A)
    return A

def Convolution_Power_LCM(A,k,L):
    """ A の lcm における k 回の畳み込みを行う.
    ただし, 最大でも L までに制限する.

    ※ A[0] の値は無視される.
    """

    A=A+[0]*(L+1-len(A))
    Divisor_Zeta_Transform(A)
    A=[pow(a,k,Mod) for a in A]
    Divisor_Mobius_Transform(A)
    return A

Mod=998244353

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page