Gcd Convolution
(Convolution/GCD_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$ の Gcd Convolution $A \oplus B$ を

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

と定義する.

Remark

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

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

Verified with

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

Code

def Multiple_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(N//p,0,-1):
                S[k*p]=0
                A[k]+=A[k*p]

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

def Multiple_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(1,N//p+1):
                S[k*p]=0
                A[k]-=A[k*p]

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

def Convolution_GCD(A,B):
    """ A,B の gcd における畳み込みを行う.

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

    N=len(A)-1; M=len(B)-1; L=max(N,M)

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

    Multiple_Zeta_Transform(A)
    Multiple_Zeta_Transform(B)

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

    Multiple_Mobius_Transform(A)
    return A

def Convolution_Power_GCD(A,k):
    """ A の gcd における k 回の畳み込みを行う.

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

    A=A[:]
    Multiple_Zeta_Transform(A)
    A=[pow(a,k,Mod) for a in A]
    Multiple_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