T1「质数埃筛」「并查集」
考场上想到了用并查集统计联通块
但怎么连接并差集只想到了$O(n^2)$的
看着1e6里面的质数个数78498，觉得没法搞
只要把每个数的所有质因子合并
其实是埃筛的思想，用埃筛求出每个点的质因子，复杂度比调和级数$O(ln)$还小
线筛可以这么打
int x=a[i]; while(x>1){
... x/=vis[x]; }
总之，1～2e9中每个数的质因子个数最多只有10个，质因子指数总和不超过30个
枚举质因子可以提前预处理，免去$O(\sqrt{n})$
T2【图上状压dp】
发现d和n都比较小
定义bool f[i][j][s]路径长度为i到达了j点，当前的状态，是否合法
发现考虑转移，状态开不下，双向搜索的技巧
定义f为正向的，定义g为反向的
dp转移枚举l ，到达点和和状态，fg分别转移即可
统计答案时只要枚举状态和以哪个点为中间点
注意分别的长度要对应，调了好久。。
原文：https://www.cnblogs.com/casun547/p/11605742.html