約数/倍数を集合とした累積和/差分
(NumberTheory/Convolution/multiple_divisor_transform.py)

• View this file on GitHub
• Last update: 2021-06-21 06:14:17+09:00

Required by

• 添字 gcd による畳み込み (NumberTheory/Convolution/gcd_convolve.py)
• 添字 lcm による畳み込み (NumberTheory/Convolution/lcm_convolve.py)

Verified with

• TestCase/unittest/multiple_divisor_transform.unittest.test.py

Code

def multiple_zeta_transform(a, op):
    n = len(a)
    res = a[:]
    prime_table = [1] * n
    for p in range(2, n):
        if not prime_table[p]:
            continue
        i = (n - 1) // p
        while i > 0:
            res[i] = op(res[i], res[i * p])
            prime_table[i * p] = 0
            i -= 1
    return res


def multiple_mobius_transform(a, op, inv):
    n = len(a)
    res = a[:]
    prime_table = [1] * n
    for p in range(2, n):
        if not prime_table[p]:
            continue
        i = 1
        while i * p < n:
            res[i] = op(res[i], inv(res[i * p]))
            prime_table[i * p] = 0
            i += 1
    return res


def divisor_zeta_transform(a, op):
    n = len(a)
    res = a[:]
    prime_table = [1] * n
    for p in range(2, n):
        if not prime_table[p]:
            continue
        i = 1
        while i * p < n:
            res[i * p] = op(res[i], res[i * p])
            prime_table[i * p] = 0
            i += 1
    return res


def divisor_mobius_transform(a, op, inv):
    n = len(a)
    res = a[:]
    prime_table = [1] * n
    for p in range(2, n):
        if not prime_table[p]:
            continue
        i = (n - 1) // p
        while i > 0:
            res[i * p] = op(inv(res[i]), res[i * p])
            prime_table[i * p] = 0
            i -= 1
    return res

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/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.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page