@[隔壁小邱](/space/show?uid=22539) 筛法预处理找因子
by moye到碗里来 @ 2018-07-21 10:02:22
@[隔壁小邱](/space/show?uid=22539)
$s$的因数个数是$O(\sqrt{s})$级别的。
那么可以先对于s的每个因数预处理它的次大因数。
然后每次询问直接查$\gcd(s,x)$的次大因数。
by 老K @ 2018-07-21 10:02:38
也许能过？
by 老K @ 2018-07-21 10:03:07
@[老K](/space/show?uid=8943) 啊，对，根号一下用筛法直接预处理因数，我反正就觉得该这么做
by moye到碗里来 @ 2018-07-21 10:04:09
计算次大因数 也就是计算最小质因子。可以先$O(\sqrt{s})$把s分解质因数，再对每个质因子判断能否整除。
by 老K @ 2018-07-21 10:04:45
@[moye到碗里来](/space/show?uid=52576) 我就是这么想的QAQ
by SkyLiYu @ 2018-07-21 10:04:47
@[老K](/space/show?uid=8943) 可以先筛法直接全部处理啊
by moye到碗里来 @ 2018-07-21 10:05:07
@[moye到碗里来](/space/show?uid=52576) 筛？不存在的
by 老K @ 2018-07-21 10:05:14
$s<=2^{31}$ 你拿啥筛啊
by 老K @ 2018-07-21 10:05:39
@[老K](/space/show?uid=8943) 你分质因子的时候筛法是可以处理根号一下的所有数的最大质因数的
by moye到碗里来 @ 2018-07-21 10:06:22