結果

問題 No.1581 Multiple Sequence
ユーザー lam6er
提出日時 2025-03-20 21:04:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 202 ms / 2,000 ms
コード長 1,159 bytes
コンパイル時間 209 ms
コンパイル使用メモリ 81,988 KB
実行使用メモリ 100,700 KB
最終ジャッジ日時 2025-03-20 21:04:41
合計ジャッジ時間 3,621 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

MOD = 10**9 + 7

def main():
    M = int(sys.stdin.readline())
    
    if M == 0:
        print(0)
        return
    
    # Maximum possible value of s is M, so s-1 can be up to M-1
    max_n = M - 1
    # Precompute divisors for all numbers up to max_n (M-1)
    divisors = [[] for _ in range(max_n + 1)]
    for d in range(1, max_n + 1):
        for multiple in range(d, max_n + 1, d):
            divisors[multiple].append(d)
    
    # Compute f(s) for all s from 1 to M
    max_s = M
    f = [0] * (max_s + 1)
    f[1] = 1  # Base case
    
    for s in range(2, max_s + 1):
        n = s - 1
        total = 0
        for d in divisors[n]:
            s_new = n // d
            if s_new >= 1:
                total += f[s_new]
        f[s] = total % MOD
    
    # Find all divisors of M
    M_divisors = set()
    for d in range(1, int(M**0.5) + 1):
        if M % d == 0:
            M_divisors.add(d)
            M_divisors.add(M // d)
    
    # Sum f(M/d) for all divisors d of M
    ans = 0
    for d in M_divisors:
        s = M // d
        ans = (ans + f[s]) % MOD
    
    print(ans % MOD)

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