結果
問題 | No.1581 Multiple Sequence |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()