没推完，以后再补充……
题目链接：https://www.luogu.com.cn/problem/P6210
定义 \(g(n, m, c)\) 表示 \([1, m]\) 中存在多少个整数 \(i\) 满足 \(\gcd(i, n) \le c\)。
则第二问的答案为 \(g(n, r, c) - g(n, l-1, c)\)。
现在考虑如何求解 \(g(n, m, c)\)：
\[g(n, m, c) = \sum_{i=1}^{m} [ \gcd(i, n) \le c ]
\]
考虑枚举 \(d = \gcd(i, n)\)，则上式转换为
\[g(n, m, c) = \sum_{d \mid n, 1 \le d \le c} \sum_{i=1}^m [\gcd(i,n) = d]
\]
将 \(d\) 从 艾弗森表达式（中括号）中提取出来，得
\[g(n, m, c) = \sum_{d \mid n, 1 \le d \le c} \sum_{i=1}^{m/d} [\gcd(i,n) = 1]
\]
接下来我们先化简一下第二个 sigma。
由 莫比乌斯反演的一个常用的性质（\([x = 1] = \sum_{e \mid x} \mu(e)\)）
我们可以将上式的最后一个 sigma 转换一下
\[\sum_{i=1}^{m/d} [\gcd(i,n) = 1]
\]
\[= \sum_{i=1}^{m/d} \sum_{e \mid \gcd(i, n)} \mu(e)
\]
我们考虑枚举 \(e\)，再考虑 \(i\)。
由于 \(e \mid \gcd(i, n)\)，所以 \(e \mid i\) \(\Rightarrow\) \(i\) 是 \(e\) 的倍数；
同时 \(i \le m / d\)。
所以，满足条件的 \(i\) 的个数为 \(\left\lfloor \frac{m/d}{e} \right\rfloor = m / (de)\) 个
所以，上面那个 sigma 转为
\[\sum_{e \mid n, e \le m/d} (m / (de)) \mu(e)
\]
代入原式得
\[g(n, m, c) = \sum_{d \mid n}^{d \le c} \sum_{e \mid n}^{e \le m/d} \mu(e) \left\lfloor \frac{ m/d }{e} \right\rfloor
\]
或者
\[g(n, m, c) = \sum_{d \mid n}^{d \le c} \sum_{e \mid n}^{e \le m/d} \mu(e) \left\lfloor \frac{ m }{de} \right\rfloor
\]
我们可以 \(O(\sqrt n)\) 得到 \(n\) 的所有约数 \(d\)（约 \(\sim O( \log n)\) 个），然后对于每个 \(d\) 整除分块 \(O(\sqrt n)\) 求出第二个 sigma 的值。