Up the Strip（前缀和/数论分块/dp）

题目 题意：对于一个数x，有两种操作，

• 减k，数x跳到 x − k , k ∈ [ 1 , x − 1 ] x-k,k\in [1,x-1] x−k,k∈[1,x−1]
• 除k, 数x跳到 ⌊ x / k ⌋ , k ∈ [ 2 , x ] \lfloor x/k \rfloor, k \in[2,x] ⌊x/k⌋,k∈[2,x] 先给定n和m，求从n跳到1有多少种跳法，答案对m取模。

思路：按着官方题解的D1思路来，减法的部分我们可以直接用前缀和维护。对于除法的部分，拆解成两个部分。 对于 k ∈ [ 2 , s q r t ( n ) ] k\in[2,sqrt(n)] k∈[2,sqrt(n)]，直接求解加起来 对于 k ∈ [ s q r t ( n ) , n ] k\in[sqrt(n),n] k∈[sqrt(n),n]，求解每个k对应的 ⌊ x / k ⌋ \lfloor x/k \rfloor ⌊x/k⌋落在 [ 2 , s q r t ( n ) ] [2,sqrt(n)] [2,sqrt(n)]的哪个区间（因为k>=sqrt(n)，必有 ⌊ x / k ⌋ \lfloor x/k \rfloor ⌊x/k⌋