/*https://nyaannyaan.github.io/library/multiplicative-function/gcd-convolution.hpp.html*/ #include #line 2 "multiplicative-function/gcd-convolution.hpp" #line 2 "multiplicative-function/divisor-multiple-transform.hpp" #include #include using namespace std; #line 2 "prime/prime-enumerate.hpp" vector prime_enumerate(int N) { vector 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 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 static void zeta_transform(vector& 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 static void mobius_transform(vector& 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 static void zeta_transform(map& 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 static void mobius_transform(map& 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 static void zeta_transform(vector& 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 static void mobius_transform(vector& 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 static void zeta_transform(map& 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 static void mobius_transform(map& 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 vector gcd_convolution(const vector& a, const vector& 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 using mint = atcoder::modint998244353; int N, M; #include using namespace std; template struct Binom { private: std::vector _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 A(M + 1); for (int i = 1; i <= N; i++) A[i] = i; vector B(M + 1); for (int i = 1; i <= M; i++) B[i] = i; auto C = gcd_convolution(A, B); mint ans; Binom 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"; }