test/yosupo/convolution/gcd_convolution.cpp

View this file on GitHub
Last update: 2025-09-20 14:41:43+07:00
Problem: https://judge.yosupo.jp/problem/gcd_convolution

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/gcd_convolution"

#include <bits/stdc++.h>
using namespace std;

#include "math/modint.hpp"
#include "math/zeta_moebius_transform.hpp"

using mint = modint998;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    vector<mint> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    auto c = gcd_convolution(a, b);
    for (int i = 1; i <= n; i++) cout << c[i] << " \n"[i == n];
}

#line 1 "test/yosupo/convolution/gcd_convolution.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/gcd_convolution"

#include <bits/stdc++.h>
using namespace std;

#line 2 "math/modint.hpp"

// clang-format off
template<uint32_t m> struct modint {
    static_assert(m >= 1, "Modulus must be in the range [1;2^31)");

    using mint = modint;
    static constexpr bool is_simple = true;

    static constexpr uint32_t mod() noexcept { return m; }
    constexpr modint() noexcept = default;
    constexpr modint(int64_t v) noexcept : _v(uint32_t((v %= m) < 0 ? v + m : v)) {}
    constexpr static mint raw(uint32_t v) noexcept { mint x; return x._v = v, x; }
    template<class T> constexpr explicit operator T() const noexcept { return _v; }

    constexpr mint &operator++() noexcept { return _v = ++_v == mod() ? 0 : _v, *this; }
    constexpr mint &operator--() noexcept { --(_v ? _v : _v = mod()); return *this; }
    constexpr mint operator++(int) noexcept { return exchange(*this, ++mint(*this)); }
    constexpr mint operator--(int) noexcept { return exchange(*this, --mint(*this)); }

    constexpr mint &operator+=(mint rhs) noexcept {
        return _v = int(_v += rhs._v - mod()) < 0 ? _v + mod() : _v, *this;
    }
    constexpr mint &operator-=(mint rhs) noexcept {
        return _v = int(_v -= rhs._v) < 0 ? _v + mod() : _v, *this;
    }
    constexpr mint &operator*=(mint rhs) noexcept {
        return _v = uint64_t(_v) * rhs._v % mod(), *this;
    }
    constexpr mint &operator/=(mint rhs) noexcept {
        return *this = *this * rhs.inv();
    }

    constexpr friend mint operator+(mint l, mint r) noexcept { return l += r; }
    constexpr friend mint operator-(mint l, mint r) noexcept { return l -= r; }
    constexpr friend mint operator*(mint l, mint r) noexcept { return l *= r; }
    constexpr friend mint operator/(mint l, mint r) noexcept { return l /= r; }

    constexpr mint operator+() const noexcept { return *this; }
    constexpr mint operator-() const noexcept { return raw(_v ? mod() - _v : 0); }

    constexpr friend bool operator==(mint l, mint r) noexcept { return l._v == r._v; }
    constexpr friend bool operator!=(mint l, mint r) noexcept { return l._v != r._v; }
    constexpr friend bool operator<(mint l, mint r) noexcept { return l._v < r._v; }

    constexpr mint pow(uint64_t n) const noexcept {
        mint b = *this, res = 1;
        while (n) n & 1 ? res *= b : 0, b *= b, n >>= 1;
        return res;
    }

    constexpr mint inv() const noexcept {
        int a = _v, b = mod(), x = 1, y = 0;
        while (b) {
            x = exchange(y, x - a / b * y);
            a = exchange(b, a % b);
        }
        assert(a == 1);
        return x;
    }

    friend istream &operator>>(istream &is, mint &x) {
        int64_t v{};
        return is >> v, x = v, is;
    }
    friend ostream &operator<<(ostream &os, const mint &x) { return os << x._v; }

  private:
    uint32_t _v = 0;
};
using modint107 = modint<1'000'000'007>;
using modint998 = modint<998'244'353>;
// clang-format on
#line 2 "math/zeta_moebius_transform.hpp"

template<class T> void multiple_fzt(vector<T> &a) {
    const int n = (int)a.size();
    vector<char> sieve(n, true);
    for (int p = 2; p < n; p += 1 + p % 2) {
        if (!sieve[p]) continue;
        for (int k = (n - 1) / p; k > 0; k--) {
            sieve[k * p] = false;
            a[k] += a[k * p];
        }
    }
}
template<class T> void multiple_fmt(vector<T> &a) {
    const int n = (int)a.size();
    vector<char> sieve(n, true);
    for (int p = 2; p < n; p += 1 + p % 2) {
        if (!sieve[p]) continue;
        for (int k = 1; k * p < n; k++) {
            sieve[k * p] = false;
            a[k] -= a[k * p];
        }
    }
}
template<class T> void divisor_fzt(vector<T> &a) {
    const int n = (int)a.size();
    vector<char> sieve(n, true);
    for (int p = 2; p < n; p += 1 + p % 2) {
        if (!sieve[p]) continue;
        for (int k = 1; k * p < n; k++) {
            sieve[k * p] = false;
            a[k * p] += a[k];
        }
    }
}
template<class T> void divisor_fmt(vector<T> &a) {
    const int n = (int)a.size();
    vector<char> sieve(n, true);
    for (int p = 2; p < n; p += 1 + p % 2) {
        if (!sieve[p]) continue;
        for (int k = (n - 1) / p; k > 0; k--) {
            sieve[k * p] = false;
            a[k * p] -= a[k];
        }
    }
}

template<class T> vector<T> gcd_convolution(vector<T> a, vector<T> b) {
    assert(a.size() == b.size());
    multiple_fzt(a), multiple_fzt(b);
    for (int i = 0; i < a.size(); i++) a[i] *= b[i];
    multiple_fmt(a);
    return a;
}
template<class T> vector<T> lcm_convolution(vector<T> a, vector<T> b) {
    assert(a.size() == b.size());
    divisor_fzt(a), divisor_fzt(b);
    for (int i = 0; i < a.size(); i++) a[i] *= b[i];
    divisor_fmt(a);
    return a;
}
#line 8 "test/yosupo/convolution/gcd_convolution.cpp"

using mint = modint998;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    vector<mint> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    auto c = gcd_convolution(a, b);
    for (int i = 1; i <= n; i++) cout << c[i] << " \n"[i == n];
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	all_zero_00	AC	5 ms	4 MB
g++	example_00	AC	4 ms	4 MB
g++	max_random_00	AC	183 ms	20 MB
g++	max_random_01	AC	184 ms	20 MB
g++	near_prime_00	AC	197 ms	20 MB
g++	near_prime_01	AC	185 ms	20 MB
g++	near_prime_02	AC	198 ms	20 MB
g++	near_prime_squared_00	AC	183 ms	20 MB
g++	near_prime_squared_01	AC	200 ms	20 MB
g++	near_prime_squared_02	AC	215 ms	20 MB
g++	random_00	AC	76 ms	10 MB
g++	random_01	AC	263 ms	11 MB
g++	random_02	AC	116 ms	13 MB
g++	small_00	AC	5 ms	4 MB
g++	small_01	AC	4 ms	4 MB
g++	small_02	AC	4 ms	4 MB
g++	small_03	AC	4 ms	4 MB
g++	small_04	AC	4 ms	4 MB
g++	small_05	AC	4 ms	4 MB
g++	small_06	AC	4 ms	4 MB
g++	small_07	AC	4 ms	4 MB
g++	small_08	AC	4 ms	4 MB
g++	small_09	AC	4 ms	4 MB
g++	small_10	AC	4 ms	4 MB
g++	small_11	AC	4 ms	4 MB
g++	small_12	AC	4 ms	4 MB
g++	small_13	AC	4 ms	4 MB
g++	small_14	AC	4 ms	4 MB
g++	small_15	AC	4 ms	4 MB
clang++	all_zero_00	AC	5 ms	4 MB
clang++	example_00	AC	4 ms	4 MB
clang++	max_random_00	AC	182 ms	20 MB
clang++	max_random_01	AC	195 ms	20 MB
clang++	near_prime_00	AC	198 ms	20 MB
clang++	near_prime_01	AC	184 ms	20 MB
clang++	near_prime_02	AC	199 ms	20 MB
clang++	near_prime_squared_00	AC	185 ms	20 MB
clang++	near_prime_squared_01	AC	186 ms	20 MB
clang++	near_prime_squared_02	AC	183 ms	20 MB
clang++	random_00	AC	75 ms	10 MB
clang++	random_01	AC	89 ms	11 MB
clang++	random_02	AC	118 ms	13 MB
clang++	small_00	AC	5 ms	4 MB
clang++	small_01	AC	4 ms	4 MB
clang++	small_02	AC	4 ms	4 MB
clang++	small_03	AC	4 ms	4 MB
clang++	small_04	AC	4 ms	4 MB
clang++	small_05	AC	4 ms	4 MB
clang++	small_06	AC	4 ms	4 MB
clang++	small_07	AC	4 ms	4 MB
clang++	small_08	AC	4 ms	4 MB
clang++	small_09	AC	4 ms	4 MB
clang++	small_10	AC	4 ms	4 MB
clang++	small_11	AC	4 ms	4 MB
clang++	small_12	AC	4 ms	4 MB
clang++	small_13	AC	4 ms	4 MB
clang++	small_14	AC	4 ms	4 MB
clang++	small_15	AC	4 ms	4 MB