1.P1447
题意：求
思考：原式等价于\(2\sum\limits_{i=1}^n\sum\limits_{j=1}^m(i,j)-n*m\)
然后套上欧拉反演即可
时间复杂度\(O(\sqrt n)\)
2.P4318
题意：\(T\) 组数据，每组数据给出一个正整数 \(K\) ，求第 \(K\) 个不含大于 1的完全平方数因子的正整数。
思考：观察答案的单调性 考虑二分答案
问题转化于如何求一个数的非平方因子数
考虑容斥 我们要减去 \(2^2,3^2,5^2\)的数 减去\(6^2,10^2,15^2\)的数，忽略\(4^2,8^2,9^2\)因子的数
容易发现容斥系数为\(\mu(x)\)
然后判断一个数是否有平方因子的公式容易得到就是\(\mu^2(i)\)
容斥一下有多少个这种数即可 时间复杂度\(O(T \sqrt n\log n )\)
3.P2303
求
考虑欧拉反演
原式等价于\(\sum\limits_{i=1}^n \sum\limits_{d|n,d|i}\varphi(d)\)
前提\(d\)的枚举 \(\sum\limits_{d|n} \sum\limits_{i=1,d|i}^n\varphi(d)\)
发现第二轮枚举于\(d\)无关 直接化简为\(\sum\limits_{d|n} (n/d)\varphi(d)\)
暴力求即可 时间复杂度\(O(\text{因数个数}\times \sqrt n)\leq O(2n)\)
即\(O(n)\).
4.P3327
设 \(d(x)\) 为 \(x\) 的约数个数，给定 \(n,m\)，求
考虑映射法
设\(\sum\limits_{x=1}^{a} p_x^k=i\)和\(\sum\limits_{y=1}^{b} p_y^k=j\)
那么若 \(i\) 有\(p^x\) \(j\) 有 \(p^y\) 则 \(ij\) 有 \(p^{x+y}\)
那么考虑这样选数：
- i能选的质因数 一定在\(i\)选 则\(p^z(z\leq x)\)
- 否则不够了 在\(j\)选 并且除以\(p^x\) 则\(p^z(z>x)\)
因此 最终取的两个因数必须互质
所以答案转化为：
\(\sum\limits_{i=1}^n \sum\limits_{j=1}^m \sum\limits_{x|i} \sum\limits_{y|j}(x,y)=1\)
然后前提\((x,y)\)的枚举
\(\sum\limits_{x=1}^n \sum\limits_{y=1}^m\sum\limits_{x|i}^n \sum\limits_{y|j}^n (x,y)=1\)
发现后面两项与\(x,y\)无关 继续化简
\(\sum\limits_{x=1}^n \sum\limits_{y=1}^m (n/x)(m/y) (x,y)=1\)
用\((i,j)\)替换一下\((x,y)\) 看到\((i,j)=1\) 考虑莫比乌斯反演
\(\sum\limits_{i=1}^n \sum\limits_{j=1}^m (n/i)(m/j) \sum\limits_{d|i,d|j}\varphi(d)\)
前提\(d\)的枚举
\(\sum\limits_{d=1}^{min(n,m)}\sum\limits_{i=1}^n \sum\limits_{j=1}^m[d|i,d|j] (n/i)(m/j)\varphi(d)\)
这个式子能继续化简
\(\sum\limits_{d=1}^{min(n,m)}\sum\limits_{i=1}^{\frac{n}{d}} \sum\limits_{j=1}^{\frac{m}{d}}(n/id)(m/jd)\varphi(d)\)
换一下顺序
\(\sum\limits_{d=1}^{min(n,m)}\varphi(d)\sum\limits_{i=1}^{\frac{n}{d}}(n/id)( \sum\limits_{j=1}^{\frac{m}{d}}m/jd)\)
定义\(f(x)\)表示 \(\sum\limits_{i=1}^x \frac{x}{i}\)
原式等于
\(\sum\limits_{d=1}^{min(n,m)}\varphi(d)f(n/d)f(m/d)\)
可以通过整除分块预处理好 \(f\) 数组 然后上面的式子也是整除分块即可
时间复杂度\(O(n\sqrt n+T\sqrt n)\)
5.P1829
题意：求
思考：转换一下 得
\(\sum\limits_{i=1}^n\sum\limits_{j=1}^m\frac{i\times j}{(i,j)}\)
转化一下\((i,j)\) 得
\(\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{d|i,d|j}([\frac{i}{d},\frac{j}{d})=1]\frac{i\times j}{d}\)
将\(d\)的枚举提前 得
\(\sum\limits_{d=1}^n\sum\limits_{i=1}^n\sum\limits_{j=1}^m(d|i,d|j)([\frac{i}{d},\frac{j}{d})=1]\frac{i\times j}{d}\)
化简一下原式 得
\(\sum\limits_{d=1}^{min(n,m)}\sum\limits_{i=1}^{n/d}\sum\limits_{j=1}^{m/d}[(i,j)=1] (i*j*d)\)
换一下系数 并带入莫比乌斯反演 得
\(\sum\limits_{x=1}^{min(n,m)}\sum\limits_{i=1}^{n/x}\sum\limits_{j=1}^{m/x}\sum\limits_{d|i,d|j} \mu(d)*i*j*x\)
将\(d\)的枚举提前 得
\(\sum\limits_{d=1}^{min(n,m)}\sum\limits_{x=1}^{min(n,m)}\sum\limits_{i=1}^{n/x}\sum\limits_{j=1}^{m/x}[d|i,d|j] \mu(d)*i*j*x\)
继续化简 得
\(\sum\limits_{d=1}^{min(n,m)}\sum\limits_{x=1}^{min(n,m)}\sum\limits_{i=1}^{n/xd}\sum\limits_{j=1}^{m/xd}\mu(d)*i*j*x*d*d\)
容易发现 这已经是最简式子 将每个式子变换一下位置
\(\sum\limits_{d=1}^{min(n,m)}\mu(d)*d*d\sum\limits_{x=1}^{min(n,m)}x\sum\limits_{i=1}^{n/xd}i\sum\limits_{j=1}^{m/xd}j\)
定义\(f(x)\)表示\(\sum\limits_{i=1}^x i\) 化简原式
\(\sum\limits_{d=1}^{min(n,m)}\mu(d)*d*d\sum\limits_{x=1}^{min(n,m)}x*f(n/xd)f(m/xd)\)
此时 式子需要优化 定义\(T=xd\) 原式等于
\(\sum\limits_{d=1}^{min(n,m)}\mu(T/x)*T/x*T/x\sum\limits_{x=1}^{min(n,m)}T/d*f(n/T)f(m/T)\)
化简成枚举\(T\) 原式等于
\(\sum\limits_{T=1}^{min(n,m)}f(n/T)f(m/T)\sum\limits_{d|T} \mu(T/d)*(T/d)^2*d\)
注意到\(n\leq 10^7\) 直接整除分块这个式子会TLE两个点 考虑优化
发现后面的式子\(\sum\limits_{d|T} \mu(T/d)*(T/d)^2*d\)完全可以优化 可以\(O(n\log \log n)\)预处理 但还是会\(T\) 怎么办？
实际上 定义 \(g(x)\) 函数为 \(\sum\limits_{d|x} \mu(x/d)*(x/d)^2*d\)
问题转化为线性求解 \(g\) 函数
容易发现 若定义 \(q(x)\) 函数为 \(\mu(x)*x^2\)
其实\(g\) 就是\(q\)函数和\(id\)函数的卷积 即 \(g=q*id\)
因为\(id\)函数是积性函数 \(q\) 函数也是积性函数 因此 \(g\) 也是积性函数 因此可以线性筛求解
怎么求呢？
考虑拆分原函数
\(g(x)=\sum\limits_{d|x} \mu(x/d)*(x/d)*x/d*d\)
\(=\sum\limits_{d|x} \mu(x/d)*(x/d)*x\)
提一下 \(x\) 得
\(=x\sum\limits_{d|x} \mu(x/d)*(x/d)\)
化简一下 得
\(=x\sum\limits_{d|x} \mu(d)*d\)
现在考虑怎么筛 肯定先不考虑 \(x\) 最后再乘上去
- 如果 \(g(x)\) 中，\(x\)为质数 容易得到为\(\mu(1)*x+1*\mu(x)=x-1\)
- 如果 \(g(x*p_j)\) 中 \(x\) \(mod\) \(p_j \ne 0\) 直接根据积性函数性质求导即可
- 如果 \(g(x*p_j)\) 中 \(x\) \(mod\) \(p_j = 0\) 因为有重复质因子时 \(mu(x)=0\) 所以只需计算所有单一质因子即可 乘上\(p_j\)就出现了重复因子 所以\(x\)已经包含了所有质因子 因此\(g(x*p_j)=g(x)\)
然后筛完乘上 \(x\) 即可
回到式子
\(\sum\limits_{T=1}^{min(n,m)}f(n/T)f(m/T)g(T)\)
整除分块一下即可 时间复杂度\(O(n+T\sqrt n)\)
6.P1891
求
\(T \leq 3*10^5\) , \(n \leq 10^6\)
大力拆式子 懒得写过程 最终结果为
\(n\sum\limits_{d|n}\sum\limits_{i=1}^d[(i,d)=1]i\)
所以我们第二个式子要求与当前的数互质的数的和
这个就不能直接套反演了 它还有一个系数\(i\)
我们思考一下质因数的特点
我们知道一个定律：\((a,n)=1 \to (a,n-a)=1(n>a)\)
所以质因数是一对对的 且每一对的和为\(n\)
所以质因数的和就是\(\varphi(n)*n/2\)
总时间复杂度\(O(n+T\sqrt n)\)