Src/Number/GCDConvolution.hpp

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

Depends on

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

Verified with

• Test/LC/gcd_convolution.test.cpp

Code

#pragma once

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

#include <algorithm>
#include <vector>

namespace zawa {

template <class T>
std::vector<T> GCDConvolution(std::vector<T> a, std::vector<T> b) {
    const usize n = std::max(a.size(), b.size());
    a.resize(n);
    b.resize(n);
    PrimeSupersetZetaTransform(a);
    PrimeSupersetZetaTransform(b);
    for (usize i = 0 ; i < n ; i++)
        a[i] *= b[i];
    PrimeSupersetMobiusTransform(a);
    return a;
}

} // namespace zawa

#line 2 "Src/Number/GCDConvolution.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 2 "Src/Number/PrimeSupersetTransform.hpp"

#line 4 "Src/Number/PrimeSupersetTransform.hpp"

#include <vector>

namespace zawa {

template <class T>
void PrimeSupersetZetaTransform(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 / i] += a[j];
            }
        }
}

template <class T>
void PrimeSupersetMobiusTransform(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 / i] -= a[j];
            }
        }
}

} // namespace zawa
#line 5 "Src/Number/GCDConvolution.hpp"

#include <algorithm>
#line 8 "Src/Number/GCDConvolution.hpp"

namespace zawa {

template <class T>
std::vector<T> GCDConvolution(std::vector<T> a, std::vector<T> b) {
    const usize n = std::max(a.size(), b.size());
    a.resize(n);
    b.resize(n);
    PrimeSupersetZetaTransform(a);
    PrimeSupersetZetaTransform(b);
    for (usize i = 0 ; i < n ; i++)
        a[i] *= b[i];
    PrimeSupersetMobiusTransform(a);
    return a;
}

} // namespace zawa

Back to top page