結果

問題 No.1973 Divisor Sequence
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:33:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 89 ms / 2,000 ms
コード長 1,850 bytes
コンパイル時間 270 ms
コンパイル使用メモリ 82,452 KB
実行使用メモリ 69,284 KB
最終ジャッジ日時 2025-03-20 20:34:38
合計ジャッジ時間 2,138 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod = 10**9 + 7

def prime_factors(m):
    factors = {}
    while m % 2 == 0:
        factors[2] = factors.get(2, 0) + 1
        m //= 2
    i = 3
    while i * i <= m:
        while m % i == 0:
            factors[i] = factors.get(i, 0) + 1
            m //= i
        i += 2
    if m > 1:
        factors[m] = 1
    return factors

def matrix_mult(a, b, mod):
    n = len(a)
    l = len(b)
    m = len(b[0]) if l > 0 else 0
    res = [[0] * m for _ in range(n)]
    for i in range(n):
        for k in range(l):
            aik = a[i][k]
            if aik == 0:
                continue
            for j in range(m):
                res[i][j] = (res[i][j] + aik * b[k][j]) % mod
    return res

def matrix_pow(mat, power, mod):
    n = len(mat)
    res = [[0] * n for _ in range(n)]
    for i in range(n):
        res[i][i] = 1
    while power > 0:
        if power % 2 == 1:
            res = matrix_mult(res, mat, mod)
        mat = matrix_mult(mat, mat, mod)
        power //= 2
    return res

def compute_case_matrix(vp, N, mod):
    if N == 0:
        return 0
    size = vp + 1
    mat = [[0] * size for _ in range(size)]
    for b in range(size):
        max_a = vp - b
        for a in range(size):
            if a <= max_a:
                mat[b][a] = 1
    if N == 1:
        total = sum(1 for _ in range(size)) % mod
        return total
    mat_pow = matrix_pow(mat, N-1, mod)
    total = 0
    for row in mat_pow:
        total = (total + sum(row)) % mod
    return total

def main():
    import sys
    input = sys.stdin.read
    N, M = map(int, input().split())
    if M == 1:
        print(1)
        return
    factors = prime_factors(M)
    result = 1
    for p, vp in factors.items():
        cnt = compute_case_matrix(vp, N, mod)
        result = (result * cnt) % mod
    print(result)

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