Src/Number/PrimeSubsetTransform.hpp

• View this file on GitHub
• Last update: 2025-09-23 17:35:06+09:00
• Include: #include "Src/Number/PrimeSubsetTransform.hpp"

Depends on

• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Required by

• Src/Number/LCMConvolution.hpp

Verified with

• Test/AtCoder/abc304_f.test.cpp
• Test/LC/lcm_convolution.test.cpp

Code

#pragma once

#include "../Template/TypeAlias.hpp"

#include <vector>

namespace zawa {

template <class T>
void PrimeSubsetZetaTransform(std::vector<T>& a) {
    std::vector<bool> p(a.size(), true);
    for (usize i = 2 ; i < a.size() ; i++)
        if (p[i]) {
            for (usize j = i ; j < a.size() ; j += i) {
                p[j] = 0;
                a[j] += a[j / i];
            }
        }
}

template <class T>
void PrimeSubsetMobiusTransform(std::vector<T>& a) {
    std::vector<bool> p(a.size(), true);
    for (usize i = 2 ; i < a.size() ; i++)
        if (p[i]) {
            for (usize j = (a.size() - 1) / i * i ; j >= i ; j -= i) {
                p[j] = 0;
                a[j] -= a[j / i];
            }
        }
}

} // namespace zawa

#line 2 "Src/Number/PrimeSubsetTransform.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Number/PrimeSubsetTransform.hpp"

#include <vector>

namespace zawa {

template <class T>
void PrimeSubsetZetaTransform(std::vector<T>& a) {
    std::vector<bool> p(a.size(), true);
    for (usize i = 2 ; i < a.size() ; i++)
        if (p[i]) {
            for (usize j = i ; j < a.size() ; j += i) {
                p[j] = 0;
                a[j] += a[j / i];
            }
        }
}

template <class T>
void PrimeSubsetMobiusTransform(std::vector<T>& a) {
    std::vector<bool> p(a.size(), true);
    for (usize i = 2 ; i < a.size() ; i++)
        if (p[i]) {
            for (usize j = (a.size() - 1) / i * i ; j >= i ; j -= i) {
                p[j] = 0;
                a[j] -= a[j / i];
            }
        }
}

} // namespace zawa

Back to top page