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

• 問題: No.3688 LCM Sum
• ユーザー: yaaya
• 提出日時: 2026-09-18 01:38:06
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: MLE
• 実行時間: -
• コード長: 4,896 bytes
• コンパイル時間: 2,712 ms
• コンパイル使用メモリ: 341,716 KB
• 実行使用メモリ: 1,304,832 KB
• 最終ジャッジ日時: 2026-09-18 01:38:18
• 合計ジャッジ時間: 7,070 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
sample	-- * 3
other	MLE * 2 -- * 9

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=a-1;i>=b;i--)
#define ll long long
#define ull unsigned ll
#define ld long double
#define bl __int128_t
#define fi first
#define se second
#define vel vector<ll>
#define vvel vector<vel>
#define pll pair<ll,ll>
#define vepll vector<pll>
#define vvepll vector<vepll>
#define ves vector<string>
#define mint Mint<998244353>
#define vem vector<mint>
#define vvem vector<vem>
#define pmm pair<mint,mint>
#define cleout(i) cout<<fixed<<setprecision(i)
template<class T>using PQ=priority_queue<T,vector<T>,greater<T>>;
//               上  右 下 左
vector<int> di={-1, 0, 1, 0};
vector<int> dj={ 0, 1, 0,-1};

vector<int> dx={ 0, 1, 0,-1};
vector<int> dy={ 1, 0,-1, 0};


vector<int> ddx={ 1, 1, 1, 0, -1, -1, -1, 0 };
vector<int> ddy={ 1, 0, -1, -1, -1, 0, 1, 1 };

ll inf=1000000000000000000;//1e18
// LLONG_MAX

mt19937_64 rng((ull)chrono::steady_clock::now().time_since_epoch().count());

template<ll P>
struct Mint{
    ll num;
    static constexpr ll MOD=P;
    Mint(ll x=0){
        if(x<0){
            x*=-1;
            x%=P;
            x=P-x;
        }
        x%=P;
        num=x;
    }
    Mint operator+(const Mint &other)const{
        return Mint(num+other.num);
    }
    Mint operator-(const Mint &other)const{
        return Mint(num-other.num);
    }
    Mint operator*(const Mint &other)const{
        return Mint(num*other.num);
    }
    Mint &operator+=(const Mint &other){
        num+=other.num;
        if(num>=P) num-=P;
        return *this;
    }
    Mint &operator-=(const Mint &other){
        num-=other.num;
        if(num<0) num+=P;
        return *this;
    }
    Mint &operator*=(const Mint &other){
        num=(num*other.num)%P;
        return *this;
    }
    Mint beki(const ll &x)const{
        Mint res=1;
        Mint now=num;
        rep(i,0,60){
            if(x&(1ll<<i)){
                res*=now;
            } 
            now*=now;
        }
        return res;
    }
    Mint inv()const{
        Mint res=1;
        Mint now=num;
        rep(i,0,30){
            if((P-2)&(1ll<<i)){
                res*=now;
            } 
            now*=now;
        }
        return res;
    }
    Mint operator/(const Mint &other)const{
        return *this*other.inv();
    }
    Mint &operator/=(const Mint &other){
        num=(num*other.inv())%P;
        return *this;
    }
    operator ll()const{
        return (ll)(num);
    }
    friend ostream& operator<<(ostream& os, const Mint& m) {
        os << m.num;
        return os;
    }
    friend istream& operator>>(istream& is, Mint& m) {
        ll x;
        is>>x;
        m=Mint(x);
        return is;
    }
};

/**
 * @brief 線形篩（素数・最小素因数・メビウス関数の列挙）
 * @details O(N)の計算量で[1,N)の範囲の素数、最小素因数、メビウス関数を同時に計算する。
 *          実行後、グローバル変数の primes に素数リストが、minprime に最小素因数が格納される。
 * @param N 探索する範囲の上限（N未満の値を計算する）
 * @return vel 各インデックスにおけるメビウス関数の値を格納した配列
 */
vel primes;
vel minprime;
vel make_mobius(ll N){
    minprime.assign(N,N);
    vel mobius(N,0);
    mobius[1]=1;
    rep(i,2,N){
        if(minprime[i]>i){
            minprime[i]=i;
            primes.push_back(i);
            mobius[i]=-1;
        }
        for(ll p:primes){
            if(p*i>=N)break;
            minprime[p*i]=p;
            if(minprime[i]==p){//i=p*xとなってる
                mobius[p*i]=0;
                break;
            }else mobius[p*i]=-mobius[i];
        }
    }
    return mobius;
}

struct CB{
    vem n,r;
    CB(ll N){//N以下のものをmod INFで返す
        n.assign(N+1,1);
        r.assign(N+1,1);
        rep(i,2,N+1){
            n.at(i)=n.at(i-1)*mint(i);
        }
        r.back()=n.back().inv();
        rrep(i,N,0) r.at(i)=r.at(i+1)*(mint)(i+1);
    }
    mint comb(ll N,ll R){//NCR
        if(N<R) return 0;
        return n.at(N)*r.at(R)*r.at(N-R);
    }
    mint P(ll N,ll R){//NPR
        return n.at(N)*r.at(N-R);
    }
};

CB cb(3.1e7);

void _solve(){
    ll N,M;
    cin>>N>>M;
    vem ans(N+1,0);
    vem f(N+1);
    vel mob=make_mobius(N+1);
    rep(i,1,N+1){
        ll now=1;
        while(now*i<N+1){
            f[now*i]+=(mint)mob[now]*cb.r[i]*cb.n[i-1];
            now++;
        }
    }
    auto g=[](ll i,ll N){
        ll m=N/i;
        return (mint)(i*(m*(m+1))/2);
    };
    mint cnt=0;
    rep(i,1,N+1){
        ans[i]=g(i,N)*g(i,M)*f[i];
        cnt+=ans[i];
    }
    cout<<cnt<<"\n";
}


int main(){
    cin.tie(nullptr);
 	ios_base::sync_with_stdio(false);

    
    ll _;
    bool multitest=0;
    if(multitest)cin>>_;
    else _=1;
    rep(__,0,_){
        _solve();
    }
}