数论练习题小结
g1ove
·
·
个人记录
1.P1447
题意：求
\sum\limits_{i=1}^n\sum\limits_{j=1}^m2\times (i,j)-1
思考：原式等价于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 (i,n)
考虑欧拉反演
原式等价于\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_{i=1}^n\sum_{j=1}^md(ij)
考虑映射法
设\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}^mlcm(i,j)
思考：转换一下 得
\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
求
\sum\limits_{i=1}^nlcm(i,n)
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)