結果

問題 No.1844 Divisors Sum Sum
ユーザー lam6er
提出日時 2025-03-20 21:12:11
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 724 ms / 3,000 ms
コード長 1,508 bytes
コンパイル時間 411 ms
コンパイル使用メモリ 82,908 KB
実行使用メモリ 131,800 KB
最終ジャッジ日時 2025-03-20 21:14:06
合計ジャッジ時間 12,626 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7
inv2 = 500000004  # Modular inverse of 2 modulo MOD

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    L = int(input[ptr])
    ptr += 1
    ans = 1
    for _ in range(L):
        P = int(input[ptr])
        e = int(input[ptr + 1])
        ptr += 2
        P_mod = P % MOD
        if P_mod == 1:
            s1 = (e + 1) % MOD
            s2 = (e % MOD) * ((e + 1) % MOD) % MOD
            s2 = s2 * inv2 % MOD
            ti = (s1 * s1 - s2) % MOD
        else:
            pow_e_plus_1 = pow(P_mod, e + 1, MOD)
            numerator_s1 = (pow_e_plus_1 - 1) % MOD
            den_s1 = (P_mod - 1) % MOD
            if den_s1 == 0:
                s1 = (e + 1) % MOD
            else:
                inv_den_s1 = pow(den_s1, MOD - 2, MOD)
                s1 = numerator_s1 * inv_den_s1 % MOD
            pow_e = pow(P_mod, e, MOD)
            term2 = ((e + 1) % MOD) * pow_e % MOD
            term3 = (e % MOD) * pow_e_plus_1 % MOD
            numerator_s2 = (1 - term2 + term3) % MOD
            numerator_s2 = numerator_s2 * P_mod % MOD
            den_sq = ((P_mod - 1) % MOD) ** 2 % MOD
            if den_sq == 0:
                s2 = 0  # Not possible in else clause
            else:
                inv_den_s2 = pow(den_sq, MOD - 2, MOD)
                s2 = numerator_s2 * inv_den_s2 % MOD
            ti = (( (e + 1) % MOD ) * s1 - s2) % MOD
        ti = ti % MOD
        ans = ans * ti % MOD
    print(ans % MOD)

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