結果

問題 No.1844 Divisors Sum Sum
ユーザー customaddonecustomaddone
提出日時 2022-03-05 00:29:45
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,500 bytes
コンパイル時間 272 ms
コンパイル使用メモリ 82,364 KB
実行使用メモリ 126,948 KB
最終ジャッジ日時 2024-07-18 23:36:52
合計ジャッジ時間 9,246 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict, deque, Counter
from heapq import heapify, heappop, heappush
import math
from copy import deepcopy
from itertools import combinations, permutations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right

import sys

def input():
    return sys.stdin.readline().rstrip()
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getListGraph():
    return list(map(lambda x:int(x) - 1, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]

mod = 10 ** 9 + 7
MOD = 998244353
# import pypyjit
# pypyjit.set_param('max_unroll_recursion=-1')
sys.setrecursionlimit(10000000)
inf = float('inf')
eps = 10 ** (-15)
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]

#############
# Main Code #
#############

def array_cnt(ar1, ar2, m):
    h = len(ar1)
    w = len(ar2[0])
    row = ar1
    col = []
    for j in range(w):
        opt = []
        for i in range(len(ar2)):
            opt.append(ar2[i][j])
        col.append(opt)

    res = [[[0, 0] for i in range(w)] for i in range(h)]
    for i in range(h):
        for j in range(w):
            cnt = 0
            for x, y in zip(row[i], col[j]):
                cnt += x * y
            res[i][j] = cnt
            res[i][j] %= m
    return res

# AにXをK回累乗する
def mat_expo(A, X, K, M):
    if K == 0:
        return A
    logk = K.bit_length()
    dp = [[[0, 0] for i in range(2)] for i in range(logk)]
    dp[0] = deepcopy(X)

    for i in range(1, logk):
        dp[i] = array_cnt(dp[i - 1], dp[i - 1], M)

    res = deepcopy(A)
    for i in range(logk):
        if K & (1 << i):
            res = array_cnt(res, dp[i], M)

    return res

"""
約数の和
例えば2^2 * 3^1 = 12の場合
2^0 * 3^0 = 1は何回数えられるか
2が2^0, 2^1, 2^2の時、3が3^0, 3^1の時数えられるので2*3回
累積していく
(2^0 * (2 - 0 + 1) + 2^1 * (2 - 1 + 1) + 2^2 * (2 - 2 + 1)) * (3^0 * (1 - 0 + 1) + 3^1 * (1 - 1 + 1))
= (2^3 - 1 + 2^2 - 1 + 2^1 - 1) / (2 - 1) * (3^2 - 1 + 3^1 - 1) / (3 - 1) (逆元はあとで求める)

1からスタートしてpでかけて1を足すをe+1回する
e+2を引く
(p-1)で割る
"""

L = getN()
ans = 1
for _ in range(L):
    p, e = getNM()
    res = [[1, 1], [0, 0]]
    t = [[p, 0], [1, 1]]
    ans *= ((mat_expo(res, t, e + 1, mod)[0][0] - (e + 2)) * pow(p - 1, mod - 2, mod)) % mod
    ans %= mod
    
print(ans)
0