#1051552 (PyPy3) No.1581 Multiple Sequence

• 問題: No.1581 Multiple Sequence
• ユーザー: 已经死了
• 提出日時: 2025-03-10 15:45:17
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 346 ms / 2,000 ms
• コード長: 5,980 bytes
• コンパイル時間: 494 ms
• コンパイル使用メモリ: 82,836 KB
• 実行使用メモリ: 97,368 KB
• 最終ジャッジ日時: 2025-03-10 15:45:26
• 合計ジャッジ時間: 8,953 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 21

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
import os,sys,random,threading
#sys.exit() 退出程序
#sys.setrecursionlimit(10**6) #调整栈空间
from random import randint,choice,shuffle
#randint(a,b)从[a,b]范围随机选择一个数
#choice(seq)seq可以是一个列表,元组或字符串,从seq中随机选取一个元素
#shuffle(x)将一个可变的序列x中的元素打乱
from copy import deepcopy
from io import BytesIO,IOBase
from types import GeneratorType
from functools import lru_cache,reduce
#reduce(op,迭代对象)
from bisect import bisect_left,bisect_right
#bisect_left(x) 大于等于x的第一个下标
#bisect_right(x) 大于x的第一个下标
from collections import Counter,defaultdict,deque
from itertools import accumulate,combinations,permutations
#accumulate(a)用a序列生成一个累积迭代器，一般list化前面放个[0]做前缀和用
#combinations(a,k)a序列选k个 组合迭代器
#permutations(a,k)a序列选k个 排列迭代器
from heapq import  heapify,heappop,heappush
#heapify将列表转为堆
from typing import Generic,Iterable,Iterator,TypeVar,Union,List
from string import ascii_lowercase,ascii_uppercase,digits
#小写字母，大写字母，十进制数字
from math import ceil,floor,sqrt,pi,factorial,gcd,log,log10,log2,inf
#ceil向上取整，floor向下取整 ，sqrt开方 ，factorial阶乘
from decimal import Decimal,getcontext
#Decimal(s) 实例化Decimal对象,一般使用字符串
#getcontext().prec=100 修改精度
from sys import stdin, stdout, setrecursionlimit
input = lambda: sys.stdin.readline().rstrip("\r\n")
MI = lambda :map(int,input().split())
li = lambda :list(MI())
ii = lambda :int(input())
mod = int(1e9 + 7) #998244353
inf = 1<<60
py = lambda :print("YES")
pn = lambda :print("NO")
DIRS = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 右下左上
DIRS8 = [(0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0),(-1, 1)]  # →↘↓↙←↖↑↗
class PrimeTable:
    def __init__(self, n=int((10**9)**0.5)+3) -> None:
        #值域1e9的话考虑质因子，只需小于等于(10**9)**0.5的质数即可
        #任意一个正整数n最多只有一个质因子大于根号n
        self.n = n
        self.primes = [] #小于等于n的所有质数
        self.min_div = [0] * (n+1)
        self.min_div[1] = 1
 
        mu = [0] * (n+1)
        phi = [0] * (n+1)
        mu[1] = 1
        phi[1] = 1
 
        for i in range(2, n+1):
            if not self.min_div[i]:
                self.primes.append(i)
                self.min_div[i] = i
                mu[i] = -1
                phi[i] = i-1
            for p in self.primes:
                if i * p > n: break
                self.min_div[i*p] = p
                if i % p == 0:
                    phi[i*p] = phi[i] * p
                    break
                else:
                    mu[i*p] = -mu[i]
                    phi[i*p] = phi[i] * (p - 1)
    # x是否质数
    def is_prime(self, x:int):
        if x < 2: return False
        if x <= self.n: return self.min_div[x] == x
        for p in self.primes:
            if p * p > x: break
            if x % p == 0: return False
        return True
    # x分解质因数:[p, cnt] 质因子p，个数cnt
    # 用的yield，当作一个可遍历的数据对象
    #一个数一定可以分解为多个质数的连乘积
    #n = x^a * y^b * z^c ...  （x,y,z为质因数） n的约数个数=(a+1)(b+1)...(y+1)
    def prime_factorization(self, x:int):
        for p in self.primes:
            if p * p > x: break
            if x <= self.n: break
            if x % p == 0:
                cnt = 0
                while x % p == 0: cnt += 1; x //= p
                yield p, cnt
        while (1 < x and x <= self.n):
            p, cnt = self.min_div[x], 0
            while x % p == 0: cnt += 1; x //= p
            yield p, cnt
        if x >= self.n and x > 1:
            #小于等于(10**9)**0.5的质数除干净了，如果还大于1
            # 那么余下的数一定是一个大于等于n的质数
            yield x, 1
            
    # x的所有因数
    def get_factors(self, x:int):
        factors = [1]
        for p, b in self.prime_factorization(x):
            n = len(factors)
            for j in range(1, b+1):
                for d in factors[:n]:
                    factors.append(d * (p ** j))
        return factors
def isprime(n):    #试除法，判断一个数是否为质数
    if n<2:
        return False
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return False
    return True
def tag_primes_eratosthenes(n):  
    # 埃氏筛,筛出[0,n)区间内的所有质数   
    # 第1e5个数字是1299709
    # 1e5前有9592个质数
    primes = [ True ]*n
    primes[ 0 ] = primes[ 1 ] = False  # 0和1不是质数
    for i in range(2,int(n**0.5)+1):
        if primes[i]:
            primes[i * i::i] = [ False ] * ((n - 1 - i * i) // i + 1)
    return primes
m=ii()
pt=PrimeTable(m+1)
#dp[n]表示和为n的合法序列个数
#假设填的是 x,a*x,a*b*x,a*b*c*x.... 这些数的和是n
#那么n一定是x的倍数，这是毋庸置疑的
#考虑枚举n的所有约数fac作为上述的x，在前面和为n-x的序列前面添上x，得到和为n的序列
#但现在问题是，不是所有的和为n-x的序列前面都可以加x的，因为他们的首项不一定是x的倍数
#既然不一定是x的倍数，那我们干脆人为的造首项一定是x的倍数，和为n-x的序列
#我们从和为(n-x)//x的转移，这些方案和我们要的是一一对应的，为什么？
#相当于我们人为的给这些序列的所有项都乘上了一个x
#那这个序列和就从(n-x)//x变成了和为n-x，而由于都乘上了x，所以第一个数一定是x的倍数
#乘上x并不会影响相邻两项后一项是前一项倍数的事实
dp=[0]*(m+10)
dp[0]=0
dp[1]=1
dp[2]=2
dp[3]=3
for i in range(4,m+1):
    dp[i]=1
    for fac in pt.get_factors(i):
        dp[i]+=dp[(i-fac)//fac]
        dp[i]%=mod
print(dp[m])
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX