結果

問題 No.3364 Push_back Operation
コンテスト
ユーザー fken_prime_57
提出日時 2025-10-27 15:43:03
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,104 bytes
コンパイル時間 3,065 ms
コンパイル使用メモリ 286,028 KB
実行使用メモリ 663,520 KB
最終ジャッジ日時 2025-11-17 20:33:37
合計ジャッジ時間 7,511 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other AC * 7 WA * 7 RE * 3 MLE * 1 -- * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;

// fast pow
ll modpow(ll a, ll e){
    ll r=1%MOD;
    a%=MOD;
    while(e){
        if(e&1) r = (__int128)r * a % MOD;
        a = (__int128)a * a % MOD;
        e >>= 1;
    }
    return r;
}

// linear sieve to get mu up to n
vector<int> mobius_sieve(int n){
    vector<int> primes;
    vector<int> mind(n+1,0);
    vector<int> mu(n+1,0);
    mu[1]=1;
    for(int i=2;i<=n;i++){
        if(!mind[i]){
            mind[i]=i;
            primes.push_back(i);
            mu[i] = -1;
        }
        for(int p:primes){
            ll v = (ll)p * i;
            if(v>n) break;
            mind[v]=p;
            if(i%p==0){
                mu[v]=0;
                break;
            }else{
                mu[v] = -mu[i];
            }
        }
    }
    return mu;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    if(!(cin>>N)) return 0;

    // 1) compute mu[1..N]
    vector<int> mu = mobius_sieve(N);
    mu[1]=1; // ensure
    // 2) prefix sum of mu for interval sums
    vector<int> pmu(N+1,0);
    for(int i=1;i<=N;i++) pmu[i] = pmu[i-1] + mu[i];

    auto mu_range_sum = [&](int l,int r)->int{
        if(r<l) return 0;
        return pmu[r] - pmu[l-1];
    };

    // cache for F(M,L) optional: map<pair(M,L), value>
    // but memory can be large; we compute on the fly, maybe memoize with unordered_map
    unordered_map<long long, ll> memo; // key = (ll)M<<32 | L  (注意 N<=1e6ならOK)

    auto key_of = [&](int M,int L)->long long{
        return ( (long long)M << 32 ) | (unsigned long long)L;
    };

    auto F = [&](int M, int L)->ll{
        if(M==0) return 0;
        long long key = key_of(M,L);
        auto it = memo.find(key);
        if(it!=memo.end()) return it->second;
        // compute sum_{k=1..M} mu(k) * floor(M/k)^L, grouping by q = floor(M/k)
        ll res = 0;
        int k=1;
        while(k<=M){
            int q = M / k;
            int r = M / q; // maximal k with floor(M/k)=q
            int mu_sum = mu_range_sum(k, r);
            if(mu_sum!=0){
                ll pw = modpow(q, L);
                ll add = ( (ll) ( (mu_sum% (int)MOD + (int)MOD ) % (int)MOD ) * pw ) % MOD;
                res += add;
                if(res>=MOD) res-=MOD;
            }
            k = r+1;
        }
        memo[key] = res%MOD;
        return res%MOD;
    };

    // enumerate d=1..N and sum over divisors L of d of F(floor(N/d), L)
    ll answer = 0;
    for(int d=1; d<=N; ++d){
        int M = N / d;
        // enumerate divisors of d
        for(int i=1; (ll)i*i<=d; ++i){
            if(d % i == 0){
                int L1 = i;
                int L2 = d / i;
                // add for L1
                ll v1 = F(M, L1);
                answer += v1; if(answer>=MOD) answer-=MOD;
                if(L2 != L1){
                    ll v2 = F(M, L2);
                    answer += v2; if(answer>=MOD) answer-=MOD;
                }
            }
        }
    }

    cout << (answer%MOD + MOD) % MOD << "\n";
    return 0;
}
0