結果

問題 No.1781 LCM
ユーザー karinohitokarinohito
提出日時 2024-11-10 06:11:46
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,084 bytes
コンパイル時間 4,268 ms
コンパイル使用メモリ 252,192 KB
実行使用メモリ 59,504 KB
最終ジャッジ日時 2024-11-10 06:12:17
合計ジャッジ時間 26,928 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 12 ms
11,648 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 AC 12 ms
11,648 KB
testcase_06 AC 12 ms
11,520 KB
testcase_07 AC 10 ms
11,392 KB
testcase_08 AC 10 ms
11,392 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 AC 9 ms
11,520 KB
testcase_12 AC 10 ms
11,520 KB
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 10 ms
11,520 KB
testcase_16 AC 12 ms
11,520 KB
testcase_17 AC 10 ms
11,640 KB
testcase_18 AC 11 ms
11,644 KB
testcase_19 WA -
testcase_20 AC 10 ms
11,648 KB
testcase_21 AC 3,363 ms
56,648 KB
testcase_22 AC 3,342 ms
56,644 KB
testcase_23 AC 11 ms
11,508 KB
testcase_24 AC 12 ms
11,488 KB
testcase_25 AC 3,358 ms
56,640 KB
testcase_26 AC 3,343 ms
56,644 KB
testcase_27 WA -
testcase_28 WA -
testcase_29 AC 770 ms
27,920 KB
testcase_30 WA -
testcase_31 AC 11 ms
11,544 KB
testcase_32 AC 10 ms
11,476 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#include<atcoder/modint>
using namespace atcoder;
using mint=modint998244353;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using ll = long long;

vector<bool> is_prime;
vector<ll> Q_enum;
vector<vector<int>> POW;
unordered_map<ll,int> 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;
}

vector<int> sm,bg;
void calc_Qenum(ll N){
    ll sq=sqrt(N);
    sm.assign(sq+1,-1);
    bg.assign(sq+1,-1);
    for(int i=1;i<=sq;i++){
        Q_enum.emplace_back(N/i);
        bg[N/(N/i)]=ID.size();
        ID[N/i]=ID.size();
        DI.push_back(N/i);
    }
    while(Q_enum.back()>1){
    	sm[Q_enum.back()-1]=ID.size();
        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=(x-1<sq?sm[x-1]:bg[N/(x-1)]);
            for(int j=0;j<sz;j++){
                ll n=Q_enum[j];
                if(n<x*x)break;
                int u=(n/x<=sq?sm[n/x]:bg[N/(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=(x<=sq?sm[x]:bg[N/(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){
                  int id=(n/c<=sq?sm[n/c]:bg[N/(n/c)]);
                    L_DP[i]+=fn(x,cnt)*(L_DP[id]-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