結果

問題 No.3607 Sum of Powers of GCDs
コンテスト
ユーザー pockyny
提出日時 2026-08-02 01:50:25
言語 C++23
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 2,893 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,499 ms
コンパイル使用メモリ 159,972 KB
実行使用メモリ 59,392 KB
最終ジャッジ日時 2026-08-02 01:50:43
合計ジャッジ時間 16,965 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")

#include <iostream>
#include <atcoder/modint>

using namespace std;
using namespace atcoder;
using mint = modint998244353;
const int MX = 1000000;
bool isPrime[MX + 10];
mint moe[MX + 10],moe_sum[MX + 10];
// k乗和の累積和 sum[i][j] = 0 ~ i - 1 までのj乗和
mint sum[MX + 10][11];
mint pw(mint a,int x){
    mint ret = 1;
    while(x){
        if(x&1) ret *= a;
        a *= a; x /= 2;
    }
    return ret;
}
mint pre_calc_pow[MX + 10];
int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    {
        int i,j;
        for(i=2;i<=MX;i++){
            if(isPrime[i]) continue;
            for(j=2*i;j<=MX;j+=i) isPrime[j] = true;
        }
        for(i=2;i<=MX;i++) isPrime[i] = !isPrime[i];
        for(i=1;i<=MX;i++) moe[i] = 1;
        for(i=2;i<=MX;i++){
            if(!isPrime[i]) continue;
            for(j=i;j<=MX;j+=i){
                if((j/i)%i==0) moe[j] = 0;
                moe[j] *= -1;
            } 
        }
        for(j=1;j<=10;j++){
            for(i=1;i<=MX + 1;i++){
                sum[i][j] = sum[i - 1][j] + pw(i - 1,j);
            }
        }
        for(i=1;i<=MX + 1;i++) moe_sum[i] = moe_sum[i - 1] + moe[i - 1];
    }
    int t; cin >> t;
    while(t){
        t--;
        int n,m,k; cin >> n >> m >> k;
        // ans = \sum_i\sum_{floor(m/x) = i}x^k(\sum_{A<=i}moe[A]*floor(i/A)^n)
        // g(i) := (\sum_{A<=i}moe[A]*floor(i/A)^n) として、floor(i/A)が同じ値ごとにまとめて計算する

        // 毎回pw(floor(i/A),n)を計算するとTLEするので、候補のO(√M)通りを先に計算 (floor(M/x)のn乗数を先に計算)
        {
            // floor(m/x) = j
            int j = 1;
            while(true){
                int l = m/(j + 1),r = m/j;
                pre_calc_pow[j] = pw(j,n);
                if(l==0) break;
                j = m/l;
            }
        }
        auto calcG = [&](int i){
            mint ret = 0;
            // floor(i/A) = j
            // -> Aj <= i < A*(j + 1)
            // -> i/(j + 1) < A <= i/j
            // -> floor(i/(j + 1)) < A <= floor(i/j)
            int j = 1;
            while(true){
                int l = i/(j + 1),r = i/j;
                // (l,r] -> [l + 1,r + 1)
                ret += (moe_sum[r + 1] - moe_sum[l + 1])*pre_calc_pow[j];
                if(l==0) break;
                j = i/l;
            }
            return ret;
        };
        mint ans = 0;
        int i = 1;
        while(i<=m){
            // floor(m/x) = i
            // -> xi <= m < x*(i + 1)
            // -> floor(m/(i + 1)) < x <= floor(m/i)
            int l = m/(i + 1),r = m/i;
            ans += (sum[r + 1][k] - sum[l + 1][k])*calcG(i);
            if(l==0) break;
            i = m/l;
        }
        cout << ans.val() << "\n";
    }
}
0