之前想到的算法竟然和LZ一模一样，不过Ai太大，于是交了暴力，没想到数据水，同求正解
by HOOCCOOH @ 2015-10-02 21:55:58
据说似乎是并查集优化的样子...
但是并不知道应该怎么做...
同暴力水过....
by Invoker @ 2015-10-02 22:12:07
感觉是pollard\_rho加线性筛优化。。。
by lyx613 @ 2015-10-02 22:25:03
就是线性筛预处理500W以内的质因数分解，然后只要rho大概2~3次就可以分解到<=500W
by lyx613 @ 2015-10-02 22:28:18
→\_→，我的算法有点神奇，链式前向星+gcd，只要自己与它最近祖先的最大公约数不为1即可
by CoolLife @ 2015-10-02 22:47:55
出题者给出的：
由于数据是随机的，所以暴力就能过。但是这里给出正解。
在初期状态和更改节点时，所有定点进行一次更新。之后所有1询问，用O(1)的方法得出。
A[i]的范围约20亿，而将其平方根后，质数约5000个。
先把A[i]全部质因数分解掉，更新的时候再计算就是了。
在这种情况下dfs树，准备好质数的栈组（一个质数准备一个栈，STL随便上），先找到它的质因数栈的栈顶元素，最大的就是答案，一边把节点编号入栈，进行下一层dfs。
虽然质数很多，但是主要集中在2,3,5,7,11,13，所以时间复杂度平均很低。
by kkksc03 @ 2015-10-02 22:50:52
@[url=/space/show?uid=4402]hjp\_handsome[/url]
十分容易卡到n^2logn
by lyx613 @ 2015-10-02 22:51:43
@[url=/space/show?uid=1]kkksc03[/url]
感觉把随机大质数乘起来能把该算法卡到nsqrtn
·····
并不清楚为什么复杂度是对的
by lyx613 @ 2015-10-02 22:53:19
@[url=/space/show?uid=1652]lyx613[/url] 一共质数就5000个，而且绝大部分在前6个质数就能解决，实际上大质数并不多。当然，仅限随机数据，如果全是大质数，那就没辙了。
by kkksc03 @ 2015-10-02 22:58:32
@[url=/space/show?uid=1]kkksc03[/url]
感觉可以rho，我来算下复杂度...
by lyx613 @ 2015-10-02 23:00:07