P5629 【AFOI-19】区间与除法

SY 好不容易才解出QM给她的数学题，在恰午饭的时候，QM 向她的脑洞里塞了个幻想的泡泡……SY 戳开一看，又是长长的一串数字! SY 实在是不想思考了，她决定用小学的除法消灭她脑洞里的数字.

定义 $op$ 操作意义为将当前数除以 $d$ 并向下取整. SY 现在有 $m$ 个“原数”，若一个数经过若干次 $op$ 操作(包括 $0$ 次)后能变为这个“原数”，那么这个数是可以被这个“原数”所消灭的。注意，“原数”是不会被消耗的. 现在 SY 想问你,对于一个区间 $[l,r]$，在消灭最多个数的前提下最少需要多少个“原数”？

无

无

#### 样例解释： **#样例1** ： $20$ 经过一次 $op$ 操作（除以 $3$ 向下取整）可以变成 $6$，而 $0$ 不能经过若干次 $op$ 操作变成 $6$ 。 所以区间 $[1,1]$ 最多消灭 $0$ 个数，消灭最多数前提下最少需要 $0$ 个 "原数"，区间 $[1,2],[2,2]$ 最多消灭 $1$ 个数，消灭最多数前提下最少需要 $1$ 个 "原数" 。 **#样例2** ： $2$ 能消灭 $\{6,19,7\}$ ， $5$ 能消灭 $\{5,15\}$ ， $10$ 能消灭 $\{10\}$ ， 所以区间 $[1,6],[1,4]$ 最少能用所有 "原数" 全部消灭，区间 $[4,6]$ 能用 $2,5$ 全部消灭。 #### 数据范围： 对于 $30\%$ 的数据：$n\le100,m\leq10, d=2, q\le 10$ 对于 $100\%$ 的数据：$n\le5\times 10^{5},m\leq60,2\leq d\leq10,q\le10^{6},0\le a_i,b_i\le 2^{63}$  特殊性质：数据经过构造。