日常艾特@[moye到碗里来](/space/show?uid=52576)
by SkyLiYu @ 2018-07-21 09:51:14
@[隔壁小邱](/space/show?uid=22539) 具体是一个什么题目呢？
另外 查找最小因数是$O(\sqrt{gcd})$的。
by 老K @ 2018-07-21 09:56:12
@[老K](/space/show?uid=8943) 哦哦，但还是很慢啊QwQ
by SkyLiYu @ 2018-07-21 09:56:56
@[隔壁小邱](/space/show?uid=22539) 具体是一个什么题目呢？
by 老K @ 2018-07-21 09:57:19
分解质因数可以用Pollard Rho加速...
by 老K @ 2018-07-21 09:57:59
```
题目描述：
初始有一个整数s，接下来有n组询问，每组询问给定一整数x，要
求你输出sgcd(s,x)，即s和x的次大公因数，若不存在则输出-1。
```
@[老K](/space/show?uid=8943)
by SkyLiYu @ 2018-07-21 09:58:34
```
对于 100%的数据，n<=500000,1<=s,x<2^31
```
by SkyLiYu @ 2018-07-21 09:58:54
@[老K](/space/show?uid=8943) 并没有听懂QAQ
by SkyLiYu @ 2018-07-21 09:59:14
@[隔壁小邱](/space/show?uid=22539) S的范围？
by moye到碗里来 @ 2018-07-21 10:00:01
@[隔壁小邱](/space/show?uid=22539) 筛法我觉得
by moye到碗里来 @ 2018-07-21 10:01:08