给定\(n,a,b,x\)四个数字，需要计数满足如下条件序列的个数(答案对\(10^9+7\)取模)，条件如下。
\[
a \le A_1 \le A_2 \le A_3 \le A_4 \le \cdots \le A_n \le b \1 \le n\le 100,1\le a,b,x \le 10^9, a\le b \\]
以及需要满足 \(lcm(A_1,A_2,A_3,\cdots ,A_n)\)可以被\(x\)整除, 即
\[
lcm(A_1,A_2,A_3,\cdots ,A_n) | x
\]
根据正难则反的原则，我们转而计数那些\(lcm\)不可以整除的序列。
仔细推断后发现，若将数\(x\)质因数分解为\(p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}\)。
那么当且仅当将某序列的\(lcm\)质因数分解后，存在某个质数的幂小于\(x\)质因数分解后(若没有对应质数就将幂视为\(0\))对应质数的幂，此序列不合法。
$$
x = p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m} \
lcm = p_1^{t_1}p_2^{t_2}\cdots p_m^{t_m} \
需要满足? k_i \le t_i (1\le i\le m)
$$
注意到没有出现在\(x\)中的质数幂对答案无影响，所以我们只考虑x分解出来的质数幂。
现在我们枚举\(lcm\)中不合法的位置，由于至少有一个位置不合法不好计算，我们利用容斥原理转而计算出单个位置不合法，两个位置不合法...m个位置不合法的方案数，即:
$$
q_i代表第i个位置合法的情况, S代表所有位置的集合{1,2,3,\cdots,m},F代表满足指定情况下的方案数\
F\left(\bigcap_{i=1}^m q_i \right) = All - F\left(\bigcup_{i=1}^m\overline{q_i} \right) \
F\left(\bigcup_{i=1}^m\overline{q_i} \right) = F(\overline{q_1})+F(\overline{q_2})+\cdots+F(\overline{q_m})\
-\sum_{1\le i<j\le m}F(\overline{q_i}\cap\overline{q_j})\
+\sum_{1\le i<j<k\le m}F(\overline{q_i}\cap\overline{q_j}\cap\overline{q_j}) \
\cdots
+\sum_{t\subseteq S}(-1)^{|t|}F\left( \bigcap_{i\in t}\overline{q_i}?\right)
$$
现在我们需要关注的就是对于一个位置集合，如何计算 \(F\left( \bigcap_{i\in t}\overline{q_i}\ \right)\)。
容易发现若\(lcm\)在这些位置不满足，则构成序列的每一个数都不是选定位置质数幂的倍数，也就是所我们首先要筛选出\([a,b]\)范围内有多少数字不是选定位置处质数幂的倍数即可。
联想在小于\(n\)的数中筛选不是\(2,3,5\)倍数的数字，我们再次利用容斥即可。
\[
G(q_i)代表[a,b]区间内不为对应i位置质数幂倍数的数字数\G\left( \bigcap_{i\subseteq t}\overline{q_i}\ \right) =(b-a+1)+\sum_{j\subseteq i}(-1)^{|j|}\left( \Big\lfloor \frac{b}{\prod_{x\in j}p_x^{k_x}}\Big\rfloor - \Big\lfloor \frac{a-1}{\prod_{x\in j}p_x^{k_x}}\Big\rfloor \right)
\]
将筛出的数字看作一个集合，大小为\(k\)，现在可以从中任意选取\(n\)个数，每个数选取次数不限，求最后构成序列的有序方案数；即计算该多重集的\(n\)组合，可构成的方案数为\(\binom{n+k-1}{n}\)（挡板法）。
\[
F\left( \bigcap_{i\subseteq t}\overline{q_i}\ \right) = \binom{G\left( \bigcap_{i\subseteq t}\overline{q_i}\ \right)+n-1}{n}
\]
整个过程需要两个容斥，做一次枚举子集即可，考虑到构成\(x\)的质数幂不超过9个，所以
ps:代码写得异常奇怪，就想试试不开数组只用vector，复杂度\(O(n2^{\omega(n)}+3^{\omega(n)})\)
```c++
#include
原文：https://www.cnblogs.com/UnderSilenceee/p/10657707.html