結果

問題 No.3505 Sum of Prod of Root
コンテスト
ユーザー gojoxd
提出日時 2026-04-18 18:57:08
言語 C
(gcc 15.2.0)
コンパイル:
gcc-15 -O2 -DONLINE_JUDGE -o a.out _filename_ -lm
実行:
./a.out
結果
WA  
実行時間 -
コード長 3,052 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 715 ms
コンパイル使用メモリ 39,020 KB
実行使用メモリ 7,972 KB
最終ジャッジ日時 2026-04-18 18:57:17
合計ジャッジ時間 5,138 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 6 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

#define MOD 998244353

long long kth_root(long long n, int k) {
    if (n == 1) return 1;
    if (k == 1) return n;
    
    long long low = 1, high = 2000000000LL;
    
    while (low < high) {
        long long mid = (low + high + 1) / 2;
        long long power = 1;
        int overflow = 0;
        
        for (int i = 0; i < k; i++) {
            if (power > n / mid) {
                overflow = 1;
                break;
            }
            power *= mid;
        }
        
        if (overflow) {
            high = mid - 1;
        } else if (power <= n) {
            low = mid;
        } else {
            high = mid - 1;
        }
    }
    
    return low;
}

long long compute_product(long long i) {
    if (i == 1) return 1;
    
    long long product = 1;
    
    for (int k = 1; k <= 63; k++) {
        long long root = kth_root(i, k);
        
        if (root == 1) break;
        
        product *= root;
    }
    
    return product;
}

int main() {
    long long N;
    scanf("%lld", &N);
    
    if (N <= 2000000) {
        // Direct computation for moderate N
        long long result = 0;
        for (long long i = 1; i <= N; i++) {
            long long prod = compute_product(i);
            result = (result + prod) % MOD;
        }
        printf("%lld\n", result);
        return 0;
    }
    
    // For very large N, use range grouping based on k-th root changes
    long long result = 0;
    long long i = 1;
    
    while (i <= N) {
        long long current_prod = compute_product(i);
        
        // Find the upper bound of the range where product stays same
        // This is determined by the next change in any k-th root
        long long max_j = N;
        
        for (int k = 2; k <= 63; k++) {
            long long root_i = kth_root(i, k);
            
            if (root_i == 1) continue;
            
            // Find where the next root occurs: (root_i + 1)^k
            long long next_root = root_i + 1;
            long long next_power = 1;
            int overflow = 0;
            
            for (int m = 0; m < k; m++) {
                if (next_power > N / next_root) {
                    overflow = 1;
                    break;
                }
                next_power *= next_root;
            }
            
            if (!overflow && next_power <= N) {
                long long boundary = next_power - 1;
                if (boundary < max_j) {
                    max_j = boundary;
                }
            }
        }
        
        long long range_end = (max_j > N) ? N : max_j;
        long long count = range_end - i + 1;
        
        // Contribute count * current_prod to result
        long long count_mod = count % MOD;
        long long prod_mod = current_prod % MOD;
        long long contribution = (count_mod * prod_mod) % MOD;
        result = (result + contribution) % MOD;
        
        i = range_end + 1;
    }
    
    printf("%lld\n", result);
    
    return 0;
}
0