houpingze 的博客

膜拜zqs,sx,zlt,ymw,qyh官方博客

CF75C 题解

分享一种常数极大的方法(

我们枚举 $1$ 到 $\sqrt{\min(a,b)}$ 中的每一个数,然后如果$i$ 是$a,b$的一个公约数,我们把它丢进数组,如果$\min(a,b)/i$ 是 $a,b$ 的一个公约数,我们也把它丢进数组。最后排个序以保证查询的二分。

然后查询的时候首先就是二分找一下现在数组里最后一个小于等于$y$的数的位置,如果符合条件就输出,否则输出 $-1$ .


2021-03-19 20:50:15 in 题解