結果

問題 No.1781 LCM
ユーザー karinohito
提出日時 2024-11-10 05:56:29
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,769 bytes
コンパイル時間 2,742 ms
コンパイル使用メモリ 220,196 KB
最終ジャッジ日時 2025-02-25 03:26:04
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other AC * 21 TLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#include<atcoder/modint>
using namespace atcoder;
using mint=modint998244353;


using ll = long long;

vector<bool> is_prime;
vector<ll> Q_enum;
vector<vector<int>> POW;
unordered_map<ll,ll> ID;
vector<ll> DI;

void enum_prime(ll N){
    ll sq=sqrt(N);
    POW.resize(sq+1);
    is_prime.assign(sq+1,1);
    is_prime[0]=is_prime[1]=0;
    for(ll i=0;i<=sq;i++){
        if(is_prime[i]){
            for(ll j=i*2;j<=sq;j+=i)is_prime[j]=0;
            ll r=1;
            int s=0;
            while(r<=N){
                s+=(r%3);
                POW[i].push_back(s%3);
                r*=i;
            }
        }
    }
    return;
}

void calc_Qenum(ll N){
    ll sq=sqrt(N);
    for(int i=1;i<=sq;i++){
        Q_enum.emplace_back(N/i);
        ID[N/i]=ID.size();
        DI.push_back(N/i);
    }
    while(Q_enum.back()>1){
        ID[Q_enum.back()-1]=ID.size();
        DI.push_back(Q_enum.back()-1);
        Q_enum.emplace_back(Q_enum.back()-1);
    }
    return;
}


ll A,B;
mint sum_n(ll n,ll c){
    if(c==1){
        return (n+2)/3-1;
    }
    if(c==2)return (n+1)/3;
    else if(c==0)return n/3;
    return 1;
}
vector<mint> calc_Fprime(ll N){
    ll sq=sqrt(N);
    int sz=Q_enum.size();
    vector<mint> F_pr(sz);
    for(int j=0;j<sz;j++){
        F_pr[j]=DI[j]-1;
    }
    for(ll x=2;x<=sq;x++){
        if(is_prime[x]){
        	int y=ID[x-1];
            for(int j=0;j<sz;j++){
                ll n=Q_enum[j];
                if(n<x*x)break;
                int u=ID[n/x];
                F_pr[j]-=mint(F_pr[u]-F_pr[y]);
            }
        }
    }
    return F_pr;
}

vector<mint> INV(100,1);

//f(p^e)
auto g_calc=[](ll p,ll e){
    return INV[e+1];
};



vector<mint> Min_sieve(ll N,function<mint(ll,ll)> fn,vector<mint> F_pr){
    int sz=Q_enum.size();
    vector<mint> L_DP(sz);
    for(int i=0;i<sz;i++)L_DP[i]=F_pr[i];
    ll sq=sqrt(N);
    for(ll x=sq;x>1;x--){
        if(is_prime[x]){
        	int y=ID[x];
            for(int i=0;i<sz;i++){
                ll n=Q_enum[i];
                if(n<x*x)break;
                ll cnt=1;
                for(ll c=x;c*x<=n;c*=x){
                    L_DP[i]+=fn(x,cnt)*(L_DP[ID[n/c]]-F_pr[y])+fn(x,cnt+1);
                    cnt++;
                }
            }
        }
    }
    return L_DP;
}

void solve(){
  ll N,M;
  cin>>N>>M;
  swap(N,M);

  for(int i=1;i<100;i++){
    INV[i]=mint(i).pow(M);
  }
  Q_enum.clear();
  ID.clear();
  DI.clear();
  calc_Qenum(N);
    vector<mint> FP=calc_Fprime(N);
    for(auto &p:FP)p*=INV[2];
    vector<mint> G_DP=Min_sieve(N,g_calc,FP);
    cout<<(G_DP[ID[N]]+1).val()<<endl;
}

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

    enum_prime(1e11+1);
    
    solve();
    
}
0