#1160236 (C++23) No.3505 Sum of Prod of Root

• 問題: No.3505 Sum of Prod of Root
• ユーザー: ,
• 提出日時: 2026-04-19 00:32:56
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 273 ms / 2,000 ms
• コード長: 4,980 bytes
• コンパイル時間: 3,769 ms
• コンパイル使用メモリ: 341,824 KB
• 実行使用メモリ: 28,020 KB
• 最終ジャッジ日時: 2026-04-19 00:33:24
• 合計ジャッジ時間: 10,210 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge2_0

ファイルパターン	結果
sample	AC * 1
other	AC * 13

ソースコード

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

const ll MOD = 998244353;

ll pw(ll b, ll e) {
    ll r=1; b%=MOD;
    for(;e>0;e>>=1){if(e&1)r=r*b%MOD; b=b*b%MOD;}
    return r;
}

const ll inv2=pw(2,MOD-2), inv6=pw(6,MOD-2), inv30=pw(30,MOD-2);
ll S2(ll n){n%=MOD;return n*(n+1)%MOD*(2*n+1)%MOD*inv6%MOD;}
ll S3(ll n){n%=MOD;ll t=n*(n+1)%MOD*inv2%MOD;return t*t%MOD;}
ll S4(ll n){n%=MOD;return n*(n+1)%MOD*(2*n+1)%MOD*((3*n%MOD*n%MOD+3*n-1+MOD)%MOD)%MOD*inv30%MOD;}
ll pref(ll m){if(m<=0)return 0;return (2*S4(m)+3*S3(m)+S2(m))%MOD;}

ll sum_i_sqrt_i(ll L, ll R) {
    if(L>R)return 0;
    ll mL=(ll)sqrtl(L); while((mL+1)*(mL+1)<=L)mL++; while(mL>0&&mL*mL>L)mL--;
    ll mR=(ll)sqrtl(R); while((mR+1)*(mR+1)<=R)mR++; while(mR>0&&mR*mR>R)mR--;
    if(mL==mR)return mL%MOD*(L%MOD+R%MOD)%MOD*((R-L+1)%MOD)%MOD*inv2%MOD;
    ll la=L,lb=(mL+1)*(mL+1)-1;
    ll lv=mL%MOD*(la%MOD+lb%MOD)%MOD*(lb-la+1)%MOD*inv2%MOD;
    ll ra=mR*mR,rb=R;
    ll rv=mR%MOD*(ra%MOD+rb%MOD)%MOD*(rb-ra+1)%MOD*inv2%MOD;
    ll mv=(pref(mR-1)-pref(mL)+MOD)%MOD;
    return (lv+mv+rv)%MOD;
}

ll safe_pow(ll v, int k, ll limit) {
    ll r=1;
    for(int i=0;i<k;i++){if(r>limit/v)return limit+1; r*=v; if(r>limit)return limit+1;}
    return r;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll N; cin>>N;
    
    // Generate change points as (position, k, new_v) triples
    // When we cross position v^k, the k-th root floor(i^{1/k}) changes from v-1 to v.
    // But wait: multiple k's can have same position (e.g., 64 = 2^6 = 4^3 = 8^2).
    // We handle all k's for a given position.
    
    // For incremental q update:
    // q = prod_{k=3}^{K} floor(i^{1/k})
    // When we enter block starting at cp = v^k:
    //   old floor(cp^{1/k}) = v-1... no wait.
    //   At cp = v^k: floor(cp^{1/k}) = v (just became v).
    //   Before cp (at cp-1): floor((cp-1)^{1/k}) = v-1.
    //   So the k-th root went from v-1 to v.
    //   Update q: q = q / (v-1) * v (mod MOD).
    //   But q/(...) is modular division: q * inv(v-1) * v.
    
    // However, multiple k's can change at the same cp!
    // We need to handle all of them.
    
    // Also, there can be change points where multiple k's change simultaneously.
    // e.g., at i=64: k=2 (8^2 -> floor changes to 8), k=3 (4^3 -> floor changes to 4),
    //                k=6 (2^6 -> floor changes to 2).
    // But we're only looking at k>=3, so at 64: k=3 changes (from 3 to 4), k=6 changes (from 1 to 2).
    
    // Wait at 64: floor(64^{1/3}) = 4, floor(63^{1/3}) = 3. Yes.
    // floor(64^{1/6}) = 2, floor(63^{1/6}) = 1. Yes.
    // floor(64^{1/4}) = floor(2.83) = 2, floor(63^{1/4}) = floor(2.82) = 2. No change.
    
    // So at position v^k, the k-th root changes. But also for divisors of k? Not necessarily.
    // We just need to track (cp, k, v) for each (v, k) pair where v^k <= N.
    
    struct CP { ll pos; int k; ll v; };
    vector<CP> cps_full;
    
    int max_k = 1;
    while((1LL << max_k) <= N) max_k++;
    
    for(int k=3; k<max_k; k++){
        for(ll v=2; ; v++){
            ll vk = safe_pow(v, k, N);
            if(vk > N) break;
            cps_full.push_back({vk, k, v});
        }
    }
    
    // Sort by position
    sort(cps_full.begin(), cps_full.end(), [](const CP& a, const CP& b){return a.pos < b.pos;});
    
    // Initial q at i=1: all floor(1^{1/k}) = 1, so q = 1.
    // Track current value of floor(i^{1/k}) for each k.
    vector<ll> cur_root(max_k + 1, 1); // cur_root[k] = current floor(i^{1/k}) for k>=3
    ll cur_q = 1; // = prod_{k>=3} cur_root[k], but all are 1 initially
    
    ll total = 0;
    ll L = 1;
    int ci = 0;
    int ncps = cps_full.size();
    
    while(L <= N){
        // Find the next change point after L (i.e., smallest cp.pos >= L that we haven't processed)
        // Actually, let's process: all change points at the same position together.
        
        ll R = N; // default: go to end
        if(ci < ncps) R = min(R, cps_full[ci].pos - 1);
        
        // Process block [L, R]
        if(L <= R){
            ll s = sum_i_sqrt_i(L, R);
            total = (total + cur_q * s) % MOD;
        }
        
        if(ci >= ncps) break;
        
        // Advance to next block: process all change points at cps_full[ci].pos
        ll next_L = cps_full[ci].pos;
        while(ci < ncps && cps_full[ci].pos == next_L){
            int k = cps_full[ci].k;
            ll v = cps_full[ci].v;
            ll old_v = cur_root[k]; // should be v-1
            // Update q: divide by old_v (if old_v >= 2), multiply by v
            if(old_v >= 2){
                cur_q = cur_q * pw(old_v, MOD-2) % MOD * (v % MOD) % MOD;
            } else {
                // old_v = 1 (contributes 1 to product), now becomes v
                cur_q = cur_q * (v % MOD) % MOD;
            }
            cur_root[k] = v;
            ci++;
        }
        L = next_L;
    }
    
    cout << total << "\n";
    return 0;
}