小技巧(3)
如何应对大量的质因数分解的询问?
如果数的大小小于$1e7$的话可以考虑先线性筛一把,再利用线性筛的$v$数组来一点一点除,单个查询复杂度跑满是$log$的。
一个结论——
有根树上一个点与一个点集内这个点的$dfn$序的前驱或后继形成的$lca$的深度是点集内所有点与之形成的$lca$中深度最大的。
又一个结论
查字符串循环节可以考虑枚举循环节大小,对总串的长度做质因数分解,挨个质因数试,看除了以后是否还为循环节,若查询为$O(1)$则总时间复杂度为$O(log(n))$
修订记录
- 2023年7月31日 创建文章