cp_library/math/table/mobius_cls.py

• View this file on GitHub
• Last update: 2025-03-30 20:17:47+09:00

Verified with

• test/atcoder/abc/abc206_e_mobius_table.test.py

Code

import cp_library.math.table.__header__

class Mobius(list[int]):
    def __init__(mu, N):
        super().__init__([0]*(N+1))
        mu[1] = 1
        for i in range(1, N+1):
            for j in range(i<<1, N+1, i):
                mu[j] -= mu[i]

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''

class Mobius(list[int]):
    def __init__(mu, N):
        super().__init__([0]*(N+1))
        mu[1] = 1
        for i in range(1, N+1):
            for j in range(i<<1, N+1, i):
                mu[j] -= mu[i]

Back to top page