#1185235 (C++23) No.3688 LCM Sum

• 問題: No.3688 LCM Sum
• ユーザー: ooaiu
• 提出日時: 2026-09-09 16:56:13
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 2,602 ms / 3,000 ms
• コード長: 5,412 bytes
• コンパイル時間: 3,068 ms
• コンパイル使用メモリ: 347,612 KB
• 実行使用メモリ: 589,500 KB
• 最終ジャッジ日時: 2026-09-09 16:56:46
• 合計ジャッジ時間: 26,562 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge3_1

ファイルパターン	結果
sample	AC * 3
other	AC * 11

ソースコード

/*https://nyaannyaan.github.io/library/multiplicative-function/gcd-convolution.hpp.html*/
#include <bits/stdc++.h>
#line 2 "multiplicative-function/gcd-convolution.hpp"

#line 2 "multiplicative-function/divisor-multiple-transform.hpp"

#include <map>
#include <vector>
using namespace std;

#line 2 "prime/prime-enumerate.hpp"

vector<int> prime_enumerate(int N) {
    vector<bool> sieve(N / 3 + 1, 1);
    for (int p = 5, d = 4, i = 1, sqn = sqrt(N); p <= sqn; p += d = 6 - d, i++) {
        if (!sieve[i]) continue;
        for (int q = p * p / 3, r = d * p / 3 + (d * p % 3 == 2), s = 2 * p,
                 qe = sieve.size();
             q < qe; q += r = s - r)
            sieve[q] = 0;
    }
    vector<int> ret{2, 3};
    for (int p = 5, d = 4, i = 1; p <= N; p += d = 6 - d, i++)
        if (sieve[i]) ret.push_back(p);
    while (!ret.empty() && ret.back() > N) ret.pop_back();
    return ret;
}
#line 8 "multiplicative-function/divisor-multiple-transform.hpp"

struct divisor_transform {
    template <typename T>
    static void zeta_transform(vector<T>& a) {
        int N = a.size() - 1;
        auto sieve = prime_enumerate(N);
        for (auto& p : sieve)
            for (int k = 1; k * p <= N; ++k) a[k * p] += a[k];
    }
    template <typename T>
    static void mobius_transform(vector<T>& a) {
        int N = a.size() - 1;
        auto sieve = prime_enumerate(N);
        for (auto& p : sieve)
            for (int k = N / p; k > 0; --k) a[k * p] -= a[k];
    }

    template <typename I, typename T>
    static void zeta_transform(map<I, T>& a) {
        for (auto p = rbegin(a); p != rend(a); p++)
            for (auto& x : a) {
                if (p->first == x.first) break;
                if (p->first % x.first == 0) p->second += x.second;
            }
    }
    template <typename I, typename T>
    static void mobius_transform(map<I, T>& a) {
        for (auto& x : a) {
            for (auto p = rbegin(a); p != rend(a); p++) {
                if (x.first == p->first) break;
                if (p->first % x.first == 0) p->second -= x.second;
            }
        }
    }
};

struct multiple_transform {
    template <typename T>
    static void zeta_transform(vector<T>& a) {
        int N = a.size() - 1;
        auto sieve = prime_enumerate(N);
        for (auto& p : sieve)
            for (int k = N / p; k > 0; --k) a[k] += a[k * p];
    }
    template <typename T>
    static void mobius_transform(vector<T>& a) {
        int N = a.size() - 1;
        auto sieve = prime_enumerate(N);
        for (auto& p : sieve)
            for (int k = 1; k * p <= N; ++k) a[k] -= a[k * p];
    }

    template <typename I, typename T>
    static void zeta_transform(map<I, T>& a) {
        for (auto& x : a)
            for (auto p = rbegin(a); p->first != x.first; p++)
                if (p->first % x.first == 0) x.second += p->second;
    }
    template <typename I, typename T>
    static void mobius_transform(map<I, T>& a) {
        for (auto p1 = rbegin(a); p1 != rend(a); p1++)
            for (auto p2 = rbegin(a); p2 != p1; p2++)
                if (p2->first % p1->first == 0) p1->second -= p2->second;
    }
};

/**
 * @brief 倍数変換・約数変換
 * @docs docs/multiplicative-function/divisor-multiple-transform.md
 */
#line 6 "multiplicative-function/gcd-convolution.hpp"

template <typename mint>
vector<mint> gcd_convolution(const vector<mint>& a, const vector<mint>& b) {
    assert(a.size() == b.size());
    auto s = a, t = b;
    multiple_transform::zeta_transform(s);
    multiple_transform::zeta_transform(t);
    for (int i = 0; i < (int)a.size(); i++) s[i] *= t[i];
    multiple_transform::mobius_transform(s);
    return s;
}

/**
 * @brief GCD畳み込み
 */

#include <atcoder/modint>
using mint = atcoder::modint998244353;
int N, M;
#include <bits/stdc++.h>
using namespace std;

template <class Mint> struct Binom {
   private:
    std::vector<Mint> _fact, _ifac;

   public:
    explicit Binom(size_t N = 0) : _fact(1, 1), _ifac(1, 1) { extend(N); }

    void extend(size_t N) {
        const size_t a = _fact.size();
        if (a > N) return;
        _fact.resize(N + 1);
        for (size_t i = a; i <= N; i++) _fact[i] = _fact[i - 1] * i;
        _ifac.resize(N + 1);
        _ifac[N] = Mint{1} / _fact[N];
        for (size_t i = N; i > a; i--) _ifac[i - 1] = _ifac[i] * i;
    }

    Mint fact(size_t x) {
        extend(x);
        return _fact[x];
    }
    Mint invfact(size_t x) {
        extend(x);
        return _ifac[x];
    }
    Mint perm(size_t N, size_t K) {
        if (N < K) return Mint{0};
        return this->fact(N) * this->invfact(N - K);
    }
    Mint comb(size_t N, size_t K) {
        if (N < K) return Mint{0};
        return this->fact(N) * this->invfact(K) * this->invfact(N - K);
    }
    Mint homo(size_t N, size_t K) {
        if (N == 0) return K == 0 ? Mint{1} : Mint{0};
        return comb(N - 1 + K, K);
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cin >> N >> M;
    if (N > M) swap(N, M);
    vector<mint> A(M + 1);
    for (int i = 1; i <= N; i++) A[i] = i;
    vector<mint> B(M + 1);
    for (int i = 1; i <= M; i++) B[i] = i;
    auto C = gcd_convolution(A, B);
    mint ans;
    Binom<mint> D(C.size());

    for (int i = 1; i < C.size(); i++) {
        ans += C[i] * D.invfact(i) * D.fact(i - 1);
    }

    cout << ans.val() << "\n";
}