結果

問題 No.3377 Sigma Index × A Problems
コンテスト
ユーザー LyricalMaestro
提出日時 2025-12-06 01:54:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,355 ms / 3,000 ms
コード長 1,327 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 525 ms
コンパイル使用メモリ 82,672 KB
実行使用メモリ 85,120 KB
最終ジャッジ日時 2025-12-06 01:54:26
合計ジャッジ時間 8,389 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

## https://yukicoder.me/problems/no/3377

MOD = 998244353

def calc_gcd(A, B):
    """
    正の整数A, Bの最大公約数を計算する
    """
    a = max(A, B)
    b = min(A, B)
    while a % b > 0:
        c = a % b
        a = b
        b = c
    return b

inv_2 = pow(2, MOD - 2, MOD)
inv_6 = pow(6, MOD - 2, MOD)

def calc_sum_k(k):
    ans = (k * (k + 1)) % MOD
    ans *= inv_2
    ans %= MOD
    return ans
    
def calc_sum_k2(k):
    ans = inv_6
    ans *= k
    ans %= MOD
    ans *= k + 1
    ans %= MOD
    ans *= 2 * k + 1
    ans %= MOD
    return ans

def solve(N):
    a_u = 1
    l = 1

    answer = 0
    while a_u <= N:
        a_l = a_u // l
        k0 = N // a_u

        ans1 = (a_l * (N + 1)) % MOD
        ans1 *= k0
        ans1 %= MOD

        ans2 = (a_u * a_l) % MOD
        ans2 *= calc_sum_k(k0)
        ans2 %= MOD
        ans2 *= -1
        ans2 %= MOD

        ans = ans1 + ans2
        ans %= MOD
        answer += ans
        answer %= MOD

        l += 1
        gcd = calc_gcd(a_u, l)
        a_u = (a_u // gcd) * l
    return answer

        
def main():
    T = int(input())
    answers = []
    for _ in range(T):
        N = int(input())
        ans = solve(N)
        answers.append(ans)
    
    for ans in answers:
        print(ans)





if __name__ == "__main__":
    main()
0