思路
首先容易发现题目相当于让你找到一个互质数对 \((a, b)\) 使得 \(l \leq a \cdot G \leq b \cdot G \leq r\), 求 \(b - a\) 最大化
然后你发现区间缩小量并不大, 简单的, 问题可以视作在一个 \(10^{18}\) 的区间里找互质数对
很快你发现, 如果从左到右扫 \(a\) , 从右到左扫 \(b\) , 应该很快就可以找到互质数对
感性理解一下, 如果你要让 \(b\) 增长 \(1\) , 那么 \(a\) 很有可能要乘上一个质数
那么直接爆搜即可
我们考虑严谨证明,
我们知道, 一个数的质数个数为 \(\log^2\) 级别的, 那么如果对于一个数 \(a\) , 必须要有另一个数 \(b\) 不能有这 \(\log^2\) 个质数
这个概率为
\[P(\text{不含所有} p_1, p_2, \dots, p_{\log^2 n}) = \prod_{i=1}^{\log^2 n} \left( 1 - \frac{1}{p_i} \right) \]这个应该也是 \(\log\) 级别的, 所以直接枚举是可行的
总结
一类利用质数出现次数为 \(\log n\) 的问题
标签：about,log,互质数,质数,leq,Problem,GCD From： https://www.cnblogs.com/YzaCsp/p/18630142