結果

問題 No.3364 Push_back Operation
コンテスト
ユーザー fken_prime_57
提出日時 2025-10-25 16:39:42
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 678 ms / 2,000 ms
コード長 2,488 bytes
コンパイル時間 422 ms
コンパイル使用メモリ 82,908 KB
実行使用メモリ 67,308 KB
最終ジャッジ日時 2025-11-17 20:31:27
合計ジャッジ時間 15,711 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 53
権限があれば一括ダウンロードができます

ソースコード

diff # 

# 法 (mod)
big2 = 998244353

def simple(n):
    """
    O(N * logN) のナイーブな実装 (C++の simple 関数に相当)
    sum_{i=1}^{n} (floor(n/i))^i
    """
    ans = 0
    for i in range(1, n + 1):
        k = n // i
        # k^i % big2 を計算
        term = pow(k, i, big2)
        ans = (ans + term) % big2
    return ans

def nosimple(n):
    """
    O(sqrt(N) * logN) の高速な実装 (C++の nosimple 関数に相当)
    """
    ans = 0
    temp = n  # 第2ループの上限 (n // (i+1) で更新)
    
    # --- 第1ループ (i*i <= n の範囲) ---
    # floor(n/i) の値が k (k <= sqrt(N)) となる i の区間についてまとめて計算
    i = 1
    while i * i <= n:
        k = i  # C++コードのループ変数 i を k (底) と読み替える
        
        up = n // k        # floor(n/i)=k となる最大の i
        down = n // (k + 1)  # floor(n/i)=k となる最小の i の一つ手前
        
        # 計算対象: sum_{j=down+1}^{up} k^j
        
        if k == 1:
            # k=1 (公比が1) の場合
            # 1 を (up - down) 回足す
            ans = (ans + (up - down)) % big2
        else:
            # k > 1 (等比数列の和の公式)
            
            # 初項 a = k^(down + 1)
            a = pow(k, down + 1, big2)
            
            # 項数 num = up - down
            num_terms = up - down
            
            # 公比の項 b = k^num
            b = pow(k, num_terms, big2)
            
            # (k-1) の逆元 (フェルマーの小定理)
            # C++の (/(i-1)) に相当
            inv_k_minus_1 = pow(k - 1, big2 - 2, big2)
            
            # a * (b - 1) * (k - 1)^-1
            term = (b - 1 + big2) % big2       # (b - 1)
            term = (term * inv_k_minus_1) % big2 # * (k - 1)^-1
            term = (a * term) % big2           # * a
            
            ans = (ans + term) % big2
        
        temp = down
        i += 1

    # --- 第2ループ (i が 1 から temp (約sqrt(N)) まで) ---
    # floor(n/i) の値が k (k > sqrt(N)) となる i について計算
    for i in range(1, temp + 1):
        k = n // i  # 底
        
        # (n/i)^i % big2
        term = pow(k, i, big2)
        ans = (ans + term) % big2
        
    return ans

# --- メイン処理 (C++の main 関数に相当) ---
if __name__ == "__main__":
    N = int(input())
    # C++のmain関数は nosimple のみを呼び出している
    print(nosimple(N))
0