如果没问题就是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