TestCase/unittest/multiple_divisor_transform.unittest.test.py

View this file on GitHub
Last update: 2021-06-21 06:14:17+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A

Depends on

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

Code

# verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A
import sys
input = sys.stdin.buffer.readline

from NumberTheory.Convolution.multiple_divisor_transform import (
    multiple_zeta_transform,
    multiple_mobius_transform,
    divisor_zeta_transform,
    divisor_mobius_transform
)


def naive_count_divisors(n):
    """O(N^2) naive calculation"""
    res = [0] * n
    for val in range(1, n):
        for div in range(1, val + 1):
            if val % div == 0:
                res[val] += 1
    return res


def naive_count_multiples(n):
    """O(N^2) naive calculation"""
    res = [0] * n
    for div in range(1, n):
        for val in range(div, n):
            if val % div == 0:
                res[div] += 1
    return res


def test(n):
    op = lambda x, y: x + y
    inv = lambda x: -x

    arr = [1] * n
    arr[0] = 0

    mul_zeta = multiple_zeta_transform(arr, op)
    naive_mul_cnt = naive_count_multiples(n)
    assert(mul_zeta == naive_mul_cnt)

    div_zeta = divisor_zeta_transform(arr, op)
    naive_div_cnt = naive_count_divisors(n)
    assert(div_zeta == naive_div_cnt)

    mul_mobius = multiple_mobius_transform(mul_zeta, op, inv)
    assert(arr == mul_mobius)

    div_mobius = divisor_mobius_transform(div_zeta, op, inv)
    assert(arr == div_mobius)


def main():
    test(1000)


if __name__ == '__main__':
    main()
    print("Hello World")

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