結果

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

ソースコード

diff # 

# 法 (mod)
big2 = 998244353

def nosimple(n):
    """
    O(sqrt(N) * logN) で sum_{i=1}^{n} (floor(n/i))^i mod big2 を計算する
    """
    ans = 0
    temp = n  # 第2ループの上限を保持する
    
    # --- 第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
        down = n // (k + 1)
        
        # floor(n/i) = k となる i の区間は [down + 1, up]
        
        # 等比数列の和: sum_{j=down+1}^{up} k^j を計算する
        # 初項 a = k^(down+1)
        # 公比 r = k
        # 項数 num = up - down
        
        a = pow(k, down + 1, big2)
        b = pow(k, up - down, big2) # k^num
        
        if k == 1:
            # k=1 の場合 (公比が1)
            # 1 を (up - down) 回足す
            ans += (up - down)
        else:
            # k > 1 の場合 (等比数列の和の公式)
            # a * (b - 1) / (k - 1)
            
            # (k-1) の逆元を求める (フェルマーの小定理)
            inv_k_minus_1 = pow(k - 1, big2 - 2, big2)
            
            # (b - 1)
            term = (b - 1 + big2) % big2 
            # * (k - 1)^-1
            term = (term * inv_k_minus_1) % big2
            # * a
            term = (a * term) % big2
            
            ans += term
            
        ans %= big2
        temp = down # C++コードの temp = n/(i+1) と同じ
        i += 1

    # --- 第2ループ (i が 1 から temp (約sqrt(N)) まで) ---
    # floor(n/i) の値が sqrt(N) より大きい i について計算
    for i in range(1, temp + 1):
        k = n // i
        if k == 0: # n/i < 1 の場合は 0^i なので 0 (i >= 1)
            continue
            
        ans += pow(k, i, big2)
        ans %= big2
        
    return ans

# --- メイン処理 ---
if __name__ == "__main__":
    N = int(input())
    print(nosimple(N))
0