#1158873 (C) No.3505 Sum of Prod of Root

• 問題: No.3505 Sum of Prod of Root
• ユーザー: 왕지후
• 提出日時: 2026-04-18 01:44:58
• 言語: C (gcc 15.2.0)
• 結果: TLE
• 実行時間: -
• コード長: 3,666 bytes
• コンパイル時間: 366 ms
• コンパイル使用メモリ: 41,344 KB
• 実行使用メモリ: 16,384 KB
• 最終ジャッジ日時: 2026-04-18 01:45:23
• 合計ジャッジ時間: 7,071 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge1_0

ファイルパターン	結果
sample	-- * 1
other	AC * 1 TLE * 1 -- * 11

ソースコード

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define MOD 998244353LL
#define MAXE 1200000
#define MAXA 1000005

typedef long long ll;
typedef __int128 i128;

typedef struct {
    ll x;      // threshold = a^k
    ll mult;   // multiply H by this at threshold
} Event;

Event ev[MAXE];
int ecnt = 0;

ll inv[MAXA];

int cmp_event(const void *a, const void *b) {
    ll x1 = ((Event *)a)->x;
    ll x2 = ((Event *)b)->x;
    if (x1 < x2) return -1;
    if (x1 > x2) return 1;
    return 0;
}

ll mod_pow(ll a, ll e) {
    ll r = 1;
    while (e > 0) {
        if (e & 1) r = (ll)((i128)r * a % MOD);
        a = (ll)((i128)a * a % MOD);
        e >>= 1;
    }
    return r;
}

ll norm(ll x) {
    x %= MOD;
    if (x < 0) x += MOD;
    return x;
}

ll sum1_mod(ll n) {
    n %= MOD;
    return (ll)((i128)n * ((n + 1) % MOD) % MOD * ((MOD + 1) / 2) % MOD);
}

ll sum2_mod(ll n) {
    ll a = n % MOD;
    ll b = (n + 1) % MOD;
    ll c = (2 * (n % MOD) + 1) % MOD;
    static const ll INV6 = 166374059LL;
    return (ll)((i128)a * b % MOD * c % MOD * INV6 % MOD);
}

ll sum3_mod(ll n) {
    ll a = n % MOD;
    ll b = (n + 1) % MOD;
    static const ll INV4 = 748683265LL;
    ll t = (ll)((i128)a * b % MOD);
    return (ll)((i128)t * t % MOD * INV4 % MOD);
}

ll sum4_mod(ll n) {
    ll a = n % MOD;
    ll b = (n + 1) % MOD;
    ll c = (2 * (n % MOD) + 1) % MOD;
    ll d = norm((3 * (i128)(n % MOD) * (n % MOD)) % MOD + 3 * (n % MOD) - 1);
    static const ll INV30 = 432572553LL;
    return (ll)((i128)a * b % MOD * c % MOD * d % MOD * INV30 % MOD);
}

// F(n) = sum_{i=1}^n i * floor(sqrt(i))
ll pref(ll n) {
    if (n <= 0) return 0;

    ll m = 0;
    while ((m + 1) <= 2000000000LL && (i128)(m + 1) * (m + 1) <= n) m++;

    ll K = m - 1;
    ll full = 0;
    if (K >= 1) {
        ll s2 = sum2_mod(K);
        ll s3 = sum3_mod(K);
        ll s4 = sum4_mod(K);
        full = norm(2 * s4 + 3 * s3 + s2);
    }

    ll mmod = m % MOD;
    ll nsum = norm(sum1_mod(n) - sum1_mod((ll)((i128)m * m - 1)));
    ll tail = (ll)((i128)mmod * nsum % MOD);

    return norm(full + tail);
}

int main(void) {
    ll N;
    scanf("%lld", &N);

    // inverses up to 1e6
    inv[1] = 1;
    for (int i = 2; i < MAXA; i++) {
        inv[i] = MOD - (ll)((i128)(MOD / i) * inv[MOD % i] % MOD);
    }

    // generate all events: threshold t = a^k (k>=3, a>=2)
    for (int k = 3; k <= 60; k++) {
        for (ll a = 2;; a++) {
            i128 p = 1;
            int ok = 1;
            for (int t = 0; t < k; t++) {
                p *= a;
                if (p > N) {
                    ok = 0;
                    break;
                }
            }
            if (!ok) break;

            ll val = (ll)p;
            ll mult = (ll)((i128)(a % MOD) * inv[a - 1] % MOD);
            ev[ecnt].x = val;
            ev[ecnt].mult = mult;
            ecnt++;
        }
    }

    qsort(ev, ecnt, sizeof(Event), cmp_event);

    ll ans = 0;
    ll H = 1;      // product_{k>=3} floor(i^(1/k)) on current interval
    ll prev = 1;   // current interval starts at prev

    int idx = 0;
    while (idx < ecnt) {
        ll x = ev[idx].x;

        if (prev <= x - 1) {
            ll seg = norm(pref(x - 1) - pref(prev - 1));
            ans = norm(ans + (ll)((i128)H * seg % MOD));
        }

        // apply all updates at threshold x
        while (idx < ecnt && ev[idx].x == x) {
            H = (ll)((i128)H * ev[idx].mult % MOD);
            idx++;
        }

        prev = x;
    }

    if (prev <= N) {
        ll seg = norm(pref(N) - pref(prev - 1));
        ans = norm(ans + (ll)((i128)H * seg % MOD));
    }

    printf("%lld\n", ans);
    return 0;
}