小技巧（3）

如何应对大量的质因数分解的询问？

如果数的大小小于$1e7$的话可以考虑先线性筛一把，再利用线性筛的$v$数组来一点一点除，单个查询复杂度跑满是$log$的。

一个结论——

有根树上一个点与一个点集内这个点的$dfn$序的前驱或后继形成的$lca$的深度是点集内所有点与之形成的$lca$中深度最大的。

又一个结论

查字符串循环节可以考虑枚举循环节大小，对总串的长度做质因数分解，挨个质因数试，看除了以后是否还为循环节，若查询为$O(1)$则总时间复杂度为$O(log(n))$