結果

問題 No.1844 Divisors Sum Sum
コンテスト
ユーザー customaddone
提出日時 2022-03-05 00:28:52
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,500 bytes
コンパイル時間 252 ms
コンパイル使用メモリ 82,968 KB
実行使用メモリ 127,480 KB
最終ジャッジ日時 2024-07-18 23:36:43
合計ジャッジ時間 10,461 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 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