#2335. 选数（number）
题意
在 \([L, H]\) （\(10^{9}\) 级别）间任选 \(n\) 个整数（可重、有序），求使得这 \(n\) 个整数的最大公因数为 \(K\) 的方案数（对 \(10^9+7\) 取模），一次询问。
题解
\[\sum_{a_1=L}^H\sum_{a_2=L}^H\cdots\sum_{a_n=L}^H[\gcd(a_1,a_2,\cdots,a_n) = K]\\
\]
枚举 GCD：
\[\sum_{d=1}^H[d=K]\sum_{a_1=\lceil\frac{L}{d}\rceil}^{\lfloor\frac{H}{d}\rfloor}\cdots\sum_{a_n=\lceil\frac{L}{d}\rceil}^{\lfloor\frac{H}{d}\rfloor}[\gcd(a_1,\cdots,a_n) = 1]
\]
去掉最前面的 \([d=K]\) 并反演：
\[\sum_{a_1=\lceil\frac{L}{K}\rceil}^{\lfloor\frac{H}{K}\rfloor}\cdots\sum_{a_n=\lceil\frac{L}{K}\rceil}^{\lfloor\frac{H}{K}\rfloor}\sum_{x|a_1,\cdots,x|a_n}\mu(x)
\]
\(\lfloor{\frac{H}{K}}\rfloor\) 和 \(\lceil\frac{L}{K}\rceil\) 太丑了，换成 \(r = \lfloor{\frac{H}{K}}\rfloor\)，\(l = \lceil\frac{L}{K}\rceil\)。
换个枚举顺序：
\[\sum_{x=1}^r\mu(x)f^n(x)
\]
其中，\(f(x)\) 表示在区间 \([l, r]\) 中有多少个数是 \(x\) 的倍数。
注意到：
\(f(x) = (\lfloor{\frac{r}{x}}\rfloor-\lceil\frac{l}{x}\rceil)+1\)
显然可以数论分块了。不过有个是上取整的数论分块。
注意到：
\[\lceil\frac{a}{b}\rceil = \lfloor\frac{a+b-1}{b}\rfloor=\lfloor\frac{a-1}{b}\rfloor+1
\]
所以对 \(\frac{l-1}{x}\) 数论分块即可。
考虑到 \(\frac{H}{K}\) 是 \(10^9\) 级别的，所以需要杜教筛。筛 \(\mu(n)\) 是板子了所以不说了。同时要记忆化每次筛出来的答案，这样才能保证「每分一块都查询一次，总共查 \(O(\sqrt n)\) 次」最后的复杂度还是对的。
时间复杂度 \(O(n^{\frac{2}{3}}+\sqrt{n}\log n)\) （默认 \(L, H, K\) 与 \(n\) 同阶）。