持续更新 做了多少东西就放多少东西）
次小质因子前缀和
【UR #13】Sanrd
设 \(f(x)\) 为 \(x\) 的次大质因子，若 \(x\) 为质数或 \(1\) 则 \(f(x)=0\)，求 \(f(x)\) 的前缀和。\(x \le 10^{11}\)
考虑 min_25 筛：首先先看一般 min_25 筛的式子，看看我们需要做什么。
\[F(x,j)=\sum_{i\ge j} f(p_i)+\sum_{\substack{k\ge j\\p_k\le \sqrt n}}\sum_{\substack{e\ge 1\\p_k^{e+1} \le n}}\left(f(p_k^e)F\left(\frac{x}{p_k^e},k+1\right)+f(p_k^{e+1})\right) \]那么我们考虑 \(f(x)\) 怎么去求：首先对于前面的质数处的点值肯定为 \(0\)，而考虑每次消一个质因子的贡献。对于形如 \(f(p_k^e\times \cdots)\) 的数，我们枚举了一个质因子，假如现在除去这个质因子就仅剩下一个质数了，那么这个数就一定是质因子，否则当前这个数就没贡献，\(f(x)=f(\frac{x}{p_k^e})\)；对于形如 \(p_k^{e+1}\) 的数，答案就是 \(p_k\)。那么我们就可以将 min_25 的式子改写为以下形式：
\[F(x,j)=\sum_{\substack{k\ge j\\p_k\le \sqrt n}}\sum_{\substack{e\ge 1\\p_k^{e+1} \le n}}\left(F\left(\frac{x}{p_k^e} + ,k+1\right)+\left(G\left(\frac{x}{p_k^e}\right) - k\right)p_k + p_k\right) \]然后直接套 min_25 筛的板子就做完了。
「LibreOJ Round #11」Misaka Network 与求和
随便推一下式子，发现题目要求的就是 \(f^k * \mu\) 的前缀和。
显然考虑杜教筛，卷一个 \(I\) 即可消去 \(\mu\)，然后再求 \(f^k\) 的前缀和，这部分直接套用上面的做法即可。
有向图判环
昨晚上想了一下，然后补一下昨天的那个判环算法。
对于每一条边，判断是否存在包括 \(u-v\) 边的环。
可以从每个点开始，考虑每个点最靠左能被哪个点到达，最靠右能被哪个点到达，这个可以直接从左到右 DFS，再从右到左 DFS 做到。然后如果这个点最靠左只能是从自己到达，最靠右也只能从自己到达，那这就不存在包含这条边的环。
标签：总结,right,20,sum,因子,ge,le,2022.11,left From： https://www.cnblogs.com/apjifengc/p/daily-2022-11-20.html