【转载】数论学习笔记(Blog of tyqtyq)

from a famous oier ( exttt{tyqtyq})请点链接tyqtyq~! - 博客园 (cnblogs.com)

数论分块

(sum_{i=1}^{n} lfloorfrac{n}{i} floor imes f(i))

在(O(n))筛出(f(i))的前缀和后, 可以在单次(O(sqrt n))的复杂度下求出上式.
考虑(lfloorfrac{n}{i} floor)的取值个数. 在 (i leq sqrt n)时最多只有(sqrt n)个(i), 故最多只有(sqrt n)个取值.

在(i>sqrt n)时, (lfloorfrac{n}{i} floor leq frac{n}{i}<sqrt n), 故最多只有(sqrt n-1)个取值.

因此我们可以考虑枚举(lfloorfrac{n}{i} floor)的取值. 因为函数不下降我们考虑枚举每个取值区间的左右端点. 不妨设某个取值区间的左端点是(l), 考虑求出该取值区间的右端点(r). 不妨设(lfloorfrac{n}{l} floor = k), 我断言(r = lfloorfrac{n}{k} floor). 因为(kr leq n leq (k+1)r), 所以必然在取值区间内. 又(k(r+1) geq n)所以(r+1)不在取值区间内. 故右端点为(r).

莫比乌斯反演

两个性质

(sumlimits_{d|n} mu(d) = [n=1]) (经常用来展开([f(n)=1]))

(sumlimits_{d|n} varphi(d) = n)

对于 (gcd) 的反演(出现(gcd)的时候枚举(gcd)也是一种时常奏效的方法):

[egin{align}f(n) &= sumlimits_{i leq a} sumlimits_{j leq b} [gcd(i, j)=n]\g(n) &= sumlimits_{n|d} f(d)\&= sumlimits_{i leq a} sumlimits_{j leq b} [n|gcd(i, j)] \&= lfloorfrac{a}{n} floor lfloorfrac{b}{n} floor\sumlimits_{n|d} mu(frac{d}{n}) g(d) &= sumlimits_{n|d} mu(frac{d}{n})sumlimits_{d|x} f(x)\&= sumlimits_{n|x} f(x) sumlimits_{frac{d}{n}|frac{x}{n}} mu(frac{d}{n})\&= sumlimits_{n|x} f(x) [x=n] = f(n)end{align} ]

对于(sigma_0)的反演

[egin{align}sigma_0(xy) &= sumlimits_{a|x}sumlimits_{b|y} [gcd(a, b)=1]\&=sumlimits_{a|x}sumlimits_{b|y}sumlimits_{d|gcd(a, b)}mu(d)end{align} ]

对于(varphi)的反演

[egin{align}varphi(ij)&=frac{varphi(i)varphi(j)gcd(i, j)}{varphi(gcd(i,j))}\&=sumlimits_{d}varphi(i)varphi(j)frac{d}{varphi(d)} [d = gcd(i, j)]\end{align} ]

反演本质

[egin{align}g(n) &= sumlimits_{d|n} f(d)\ f(n) &= sumlimits_{d|n} [frac{n}{d}=1]f(d) \ &= sumlimits_{d|n} sumlimits_{id|n} mu(i)f(d) \ &=sumlimits_{i|n} mu(i) sumlimits_{d|frac{n}{i}} f(d) \ &=sumlimits_{d|n} mu(d) f(frac{n}{d}) = sumlimits_{d|n} mu(frac{n}{d}) f(d) end{align} ]

狄利克雷卷积 与 杜教筛

下文中的(A),(B),(C)均指某积性函数.

狄利克雷卷积

定义:

(A*B(n) = sumlimits_{d|n} A(d)B(frac{n}{d}))

几个常用的卷积

(varphi *I = id)

(mu * I = epsilon)

(epsilon * A = A)

(A*(B*C) = (A*B)*C)

(A*B = B*A)

((A+B)*C = A*C+B*C)

杜教筛的原理

设(A = B*C), 于是有

[egin{align}sumlimits_{i=1}^{n} A(i) &= sumlimits_{i=1}^{n} sumlimits_{d|i} C(d) B(frac{i}{d})\&=sumlimits_{d=1}^{n}C(d)sumlimits_{k=1}^{lfloorfrac{n}{d} floor}B(k)end{align} ]

不妨设(S(n) = sumlimits_{i=1}^{n} B(i))所以(C(1)S(n) = sumlimits_{i=1}^{n}A(i) - sumlimits_{d=2}^{n}C(d)S(lfloorfrac{n}{d} floor))

若选择一个较好的(C)和(A), 则可以通过数论分块在(T(n) = O(frac{n}{sqrt m}+m))的时间复杂度内完成此问题, 其中(m)是一个常数, 代表我们需要先使用线性筛筛出(S(1sim m)), 可以发现在(m = n^{frac23})时算法复杂度为(O(n^frac23))为最优.