如果没问题就是300
T1
线性筛里，每个数都会被他最小的质因数筛到，令
\(f(x)=[x\%p==0] \quad p \in dangerous\)
这显然是个完全积性函数，线性筛即可
时间复杂度:\(O(n)\)
T2
考虑这棵树实质上是一个以1为根，边权为大于父亲边权的质数，节点值则为到根路径上边权累乘
那么我们要求x，y之间路径实质上是\(dep[x]+dep[y]-dep[lca]*2+1\)
lca则是x，y相同最多的最小质因数
比如 111 555
111 = 3 * 37
555 = 3 * 5 * 37
LCA(111,555)=3
每个数最小质因数显然也可以线性筛直接求
时间复杂度：\(O(n\log n)\)
T3
考虑直接枚举\(\frac{y+x}{y-x}\)的值
设\(c1=y+x\quad c2=y-x\)
\[y=\frac{c1+c2}{2}\quad x=\frac{c1-c2}{2} \]值最大到2n-1
可以证明，我们每次枚举到的都是可能的x，y，这样的最多4n组，时间复杂度\(O(4n)\)
标签：7.29,day6,复杂度,frac,555,数学,quad,c2,质因数 From： https://www.cnblogs.com/Linnyx/p/17589341.html