#ifdef NACHIA #define _GLIBCXX_DEBUG #else // disable assert #define NDEBUG #endif #include #include #include #include #include using namespace std; using ll = long long; const ll INF = 1ll << 60; #define REP(i,n) for(ll i=0; i using V = vector; template void chmax(A& l, const B& r){ if(l < r) l = r; } template void chmin(A& l, const B& r){ if(r < l) l = r; } #include namespace nachia{ namespace prime_sieve_explicit_internal{ std::vector isprime = { false }; // a[x] := isprime(2x+1) void CalcIsPrime(int z){ if((int)isprime.size() *2+1 < z+1){ int new_z = isprime.size(); while(new_z*2+1 < z+1) new_z *= 2; z = new_z-1; isprime.resize(z+1, true); for(int i=1; i*(i+1)*2<=z; i++) if(isprime[i]){ for(int j=i*(i+1)*2; j<=z; j+=i*2+1) isprime[j] = false; } } } std::vector prime_list = {2}; int prime_list_max = 0; void CalcPrimeList(int z){ while((int)prime_list.size() < z){ if((int)isprime.size() <= prime_list_max + 1) CalcIsPrime(prime_list_max * 2 + 10); for(int p=prime_list_max+1; p<(int)isprime.size(); p++){ if(isprime[p]) prime_list.push_back(p*2+1); } prime_list_max = isprime.size() - 1; } } void CalcPrimeListUntil(int z){ if(prime_list_max < z){ CalcIsPrime(z); for(int p=prime_list_max+1; p<(int)isprime.size(); p++){ if(isprime[p]) prime_list.push_back(p*2+1); } prime_list_max = isprime.size() - 1; } } } bool IsprimeExplicit(int n){ using namespace prime_sieve_explicit_internal; if(n == 2) return true; if(n % 2 == 0) return false; CalcIsPrime(n); return isprime[(n-1)/2]; } int NthPrimeExplicit(int n){ using namespace prime_sieve_explicit_internal; CalcPrimeList(n); return prime_list[n]; } int PrimeCountingExplicit(int n){ using namespace prime_sieve_explicit_internal; if(n < 2) return 0; CalcPrimeListUntil(n); auto res = std::upper_bound(prime_list.begin(), prime_list.end(), n) - prime_list.begin(); return (int)res; } // [l, r) std::vector SegmentedSieveExplicit(long long l, long long r){ assert(0 <= l); assert(l <= r); long long d = r - l; if(d == 0) return {}; std::vector res(d, true); for(long long p=2; p*p<=r; p++) if(IsprimeExplicit(p)){ long long il = (l+p-1)/p, ir = (r+p-1)/p; if(il <= p) il = p; for(long long i=il; i void DivisorZeta(std::vector& a){ int n = a.size() - 1; for(int d=2; d<=n; d++) if(IsprimeExplicit(d)) for(int i=1; i*d<=n; i++) a[i*d] += a[i]; } template void DivisorReversedZeta(std::vector& a){ int n = a.size() - 1; for(int d=2; d<=n; d++) if(IsprimeExplicit(d)) for(int i=n/d; i>=1; i--) a[i] += a[i*d]; } template void DivisorMobius(std::vector& a){ int n = a.size() - 1; for(int d=2; d<=n; d++) if(IsprimeExplicit(d)) for(int i=n/d; i>=1; i--) a[i*d] -= a[i]; } template void DivisorReversedMobius(std::vector& a){ int n = a.size() - 1; for(int d=2; d<=n; d++) if(IsprimeExplicit(d)) for(int i=1; i*d<=n; i++) a[i] -= a[i*d]; } template std::vector GcdConvolution(std::vector a, std::vector b){ assert(a.size() == b.size()); assert(1 <= a.size()); DivisorReversedZeta(a); DivisorReversedZeta(b); for(int i=1; i<(int)a.size(); i++) a[i] *= b[i]; DivisorReversedMobius(a); return a; } template std::vector LcmConvolution(std::vector a, std::vector b){ assert(a.size() == b.size()); assert(1 <= a.size()); DivisorZeta(a); DivisorZeta(b); for(int i=1; i<(int)a.size(); i++) a[i] *= b[i]; DivisorMobius(a); return a; } template void SumForCoprimeIndex(std::vector& f){ if((int)f.size() <= 1) return; Elem q = f[1]; for(int i=2; i<(int)f.size(); i++) q += f[i]; std::vector F(f.size()); F[1] = -1; DivisorMobius(F); DivisorReversedZeta(f); f[1] -= f[1]; Elem t = f[1]; for(int i=2; i<(int)f.size(); i++){ if(F[i] == 0) f[i] = f[1]; if(F[i] == -1){ t = f[1]; t -= f[i]; f[i] = t; } } DivisorZeta(f); for(int i=1; i<(int)f.size(); i++){ t = q; t -= f[i]; f[i] = t; } } } // namespace nachia #include namespace nachia{ // ax + by = gcd(a,b) // return ( x, - ) std::pair ExtGcd(long long a, long long b){ long long x = 1, y = 0; while(b){ long long u = a / b; std::swap(a-=b*u, b); std::swap(x-=y*u, y); } return std::make_pair(x, a); } } // namespace nachia namespace nachia{ template struct StaticModint{ private: using u64 = unsigned long long; unsigned int x; public: using my_type = StaticModint; template< class Elem > static Elem safe_mod(Elem x){ if(x < 0){ if(0 <= x+MOD) return x + MOD; return MOD - ((-(x+MOD)-1) % MOD + 1); } return x % MOD; } StaticModint() : x(0){} StaticModint(const my_type& a) : x(a.x){} StaticModint& operator=(const my_type&) = default; template< class Elem > StaticModint(Elem v) : x(safe_mod(v)){} unsigned int operator*() const { return x; } my_type& operator+=(const my_type& r) { auto t = x + r.x; if(t >= MOD) t -= MOD; x = t; return *this; } my_type operator+(const my_type& r) const { my_type res = *this; return res += r; } my_type& operator-=(const my_type& r) { auto t = x + MOD - r.x; if(t >= MOD) t -= MOD; x = t; return *this; } my_type operator-(const my_type& r) const { my_type res = *this; return res -= r; } my_type operator-() const noexcept { my_type res = *this; res.x = ((res.x == 0) ? 0 : (MOD - res.x)); return res; } my_type& operator*=(const my_type& r){ x = (u64)x * r.x % MOD; return *this; } my_type operator*(const my_type& r) const { my_type res = *this; return res *= r; } bool operator==(const my_type& r) const { return x == r.x; } my_type pow(unsigned long long i) const { my_type a = *this, res = 1; while(i){ if(i & 1){ res *= a; } a *= a; i >>= 1; } return res; } my_type inv() const { return my_type(ExtGcd(x, MOD).first); } unsigned int val() const { return x; } int hval() const { return int(x > MOD/2 ? x - MOD : x); } static constexpr unsigned int mod() { return MOD; } static my_type raw(unsigned int val) { auto res = my_type(); res.x = val; return res; } my_type& operator/=(const my_type& r){ return operator*=(r.inv()); } my_type operator/(const my_type& r) const { return operator*(r.inv()); } }; } // namespace nachia using Mint = nachia::StaticModint<998244353>; void testcase(){ ll N, M; cin >> N >> M; V A(max(N,M)+1); for(ll i=1; i<=N; i++) A[i] = i; nachia::SumForCoprimeIndex(A); Mint ans = 0; for(ll i=1; i<=M; i++) ans += A[i] * i; cout << ans.val() << "\n"; } int main(){ cin.tie(0)->sync_with_stdio(0); testcase(); return 0; }