Daniel_yuan's Blog

题面在此。

一些神题。

众所周知在 c++11 中支持了同 python3 一样的范围 for 语句。即 for (int x : vector)。

该语法结合 c++11 中方便的 auto 不定类型名使用体验极佳。

大佬说 Euler-Project 没有刷的必要，这篇博客咕了。

琢磨了一下午，在输入输出流上面有了一点点自己的理解。

求 \(\sum_{i=1}^N\sum_{j=1}^Nf^k(\gcd(i,j))\)，其中 \(f(x)\) 表示 \(x\) 的第二大质因子，每个质因子算多次，即 \(f(4)=f(6)=2\)，定义 \(f(1)=0,f(Prime)=1\)。

众所周知 Min_25 筛的本质是用 DP 求出所有 \(S(\lfloor\frac{n}{1}\rfloor),S(\lfloor\frac{n}{2}\rfloor)...\) 这 \(2\sqrt{n}\) 个值。如果可以较好的处理每个数质因子之间的关系的话，是不要求所筛函数是积性函数的，这个题就是一个典型例子。

不难发现就是求 \(A*B^C\) 的长度为 \(n\) 的循环卷积（这都看不出来还配做这个题？）

白兔虐我千百遍，我待白兔如初恋。

随着单位根反演的普及，这道题或许会逐渐成为模板。

好像网上没有这么做的题解，所以就写个吧。