Project Euler 439
Project Euler 439
题目
Sum of sum of divisors
Let \(d(k)\) be the sum of all divisors of \(k\).
We define the function \(S(N) = \sum_{i=1}^N \sum_{j=1}^Nd(i \cdot j)\).
For example, \(S(3) = d(1) + d(2) + d(3) + d(2) + d(4) + d(6) + d(3) + d(6) + d(9) = 59\).
You are given that \(S(10^3) = 563576517282\) and \(S(10^5) \bmod 10^9 = 215766508\).
Find \(S(10^{11}) \bmod 10^9\).
解决方案
对质数幂 \(p^k\)，约数和为等比数列：\(d(p^k)=1+p+p^2+\cdots+p^k=\dfrac{p^{k+1}-1}{p-1}.\)
令 \(a,b\ge 0\)，直接相乘：\(\displaystyle{d(p^a)d(p^b)=\left(\sum_{x=0}^{a}p^x\right)\left(\sum_{y=0}^{b}p^y\right)=\sum_{t=0}^{a+b} c_t p^t,}\)其中系数 \(c_t\) 是满足 \(x+y=t\) 的解的个数。
注意到\(\displaystyle{pd(p^{a-1})d(p^{b-1})=p\left(\sum_{x=0}^{a-1}p^x\right)\left(\sum_{y=0}^{b-1}p^y\right)=\sum_{t=1}^{a+b-1} c'_t p^t,}\) 其中 \(c'_t\) 正好对应“既能从左取至少 1 次，又能从右取至少 1 次”的那部分。因此相减会把中间重复的项抵消，只留下
\[ d(p^{a+b}) = d(p^a)d(p^b) - pd(p^{a-1})d(p^{b-1}). \]
这就是后续所有化简的核心。
记 \(\mu(n)\) 为 Möbius 函数。我们希望得到一个把 \(d(ij)\) 按 \(\gcd(i,j)\) 分解的式子。
令 \(i,j\) 的某个质因子 \(p\) 的指数分别为 \(a=v_p(i),b=v_p(j)\)。则\(v_p(ij)=a+b, v_p(\gcd(i,j))=\min(a,b).\)
考虑下面这个局部求和：\(\displaystyle{\sum_{t=0}^{\min(a,b)} p^t\mu(p^t)d(p^{a-t})d(p^{b-t}).}\) 由于 当 \(t\ge 2\)时，\(\mu(p^t)=0\)，所以式子只有两项：\(d(p^a)d(p^b) - pd(p^{a-1})d(p^{b-1}) = d(p^{a+b}).\)这正好等于 \(d(p^{v_p(ij)})\)。
因为 \(d(\cdot)\) 与 \(\mu(\cdot)\) 都是乘法函数，这个对每个质数成立的分解可以乘起来，得到对任意 \(i,j\) 的恒等式：
\[ d(ij)=\sum_{k\mid \gcd(i,j)} k\mu(k)d\left(\frac{i}{k}\right)d\left(\frac{j}{k}\right). \]
把上式代回 \(S(N)\)：\(\displaystyle{S(N)=\sum_{i\le N}\sum_{j\le N}\sum_{k\mid \gcd(i,j)} k\mu(k)d(i/k)d(j/k).}\)交换求和顺序。对固定 \(k\)，令 \(i=kx,j=ky\)，则 \(x,y\le N/k\)： \[ S(N)=\sum_{k\le N} k\mu(k)\left(\sum_{x\le N/k}d(x)\right)\left(\sum_{y\le N/k}d(y)\right). \]
定义\(\displaystyle{D(Q)=\sum_{n\le Q} d(n),}\)则
\[ S(N)=\sum_{k=1}^{N} k\mu(k)D\left(\left\lfloor\frac{N}{k}\right\rfloor\right)^2. \]
可见，对于小于等于\(Q\)的整数中，有\(\left\lfloor\dfrac{D}{t}\right\rfloor\)个因子为\(r\)。因此\(\displaystyle{D(Q)=\sum_{t=1}^{Q} t\Big\lfloor\frac{Q}{t}\Big\rfloor.}\)这正是一个典型可用数论分块双曲线方法加速的求和，后面我们介绍一个关于\(Q\)的一个数论分块递推来减少算多次\(Q(\cdot)\)的时间。
5. 定义并计算 \(F(Q)=\sum_{k\le Q} k\mu(k)\)
令\(\displaystyle{F(Q)=\sum_{k\le Q} k\mu(k).}\)把\(i(n)=n\)和\(\mu(n)\)的卷积写出来：\(\displaystyle{\sum_{k\le n} kF\left(\left\lfloor\frac{n}{k}\right\rfloor\right)= \sum_{k\le n} k\sum_{d\le n/k} d\mu(d)= \sum_{kd\le n} kd,\mu(d)= \sum_{m\le n} m\sum_{d\mid m}\mu(d).}\)
而\(\displaystyle{\sum_{d\mid m}\mu(d)=\begin{cases}1,&m=1\\0,&m>1\end{cases}}\)，所以整个卷积和恒等于 1：
\[ \sum_{k=1}^{n} kF\left(\left\lfloor\frac{n}{k}\right\rfloor\right)=1. \]
移项即可得到递推，可以用数论分块来完成：
\[ F(n)=1-\sum_{k=2}^{n} kF\left(\left\lfloor\frac{n}{k}\right\rfloor\right). \]
为了满足\(D(\cdot)\)能够被高效计算的需求，我们接下来证明下面的Dirichlet卷积是成立的：
\[ \sum_{k=1}^{n} k\mu(k)D\left(\left\lfloor\frac{n}{k}\right\rfloor\right)=n. \]
把上面的 \(\displaystyle{D(Q)=\sum_{t\le Q} t\left\lfloor\dfrac{Q}{r}\right\rfloor}\) 代进去，其中 \(Q=\left\lfloor\dfrac{n}{k}\right\rfloor\)：
\[ \sum_{k\le n} k\mu(k)D\left(\left\lfloor\frac{n}{k}\right\rfloor\right) =\sum_{k\le n} k\mu(k)\sum_{t\le \lfloor n/k\rfloor} t\left\lfloor\frac{\lfloor n/k\rfloor}{t}\right\rfloor. \]
注意一个关键：对整数 \(t\)，\(\left\lfloor\dfrac{\lfloor n/k\rfloor}{t}\right\rfloor=\left\lfloor\dfrac{n}{kt}\right\rfloor.\)所以右边变成：\(\displaystyle{\sum_{k\le n} k\mu(k)\sum_{t\le n/k} t\left\lfloor\frac{n}{kt}\right\rfloor.}\)
我们现在把双重求和合并成对所有满足 \(kt\le n\) 的配对求和，那么左边得到\(\displaystyle{\sum_{kt\le n} k\mu(k)t\left\lfloor\frac{n}{kt}\right\rfloor.}\)
现在令\(m=kt,\)则 \(m\le n\)，并且对固定的 \(m\)，所有 \((k,t)\) 满足 \(kt=m\) 等价于枚举 \(k\mid m\)，且 \(t=m/k\)。代入左边得到：\(\displaystyle{\sum_{m\le n}\sum_{k\mid m} k\mu(k)\cdot \frac{m}{k}\cdot \left\lfloor\frac{n}{m}\right\rfloor=\sum_{m\le n} m\left\lfloor\frac{n}{m}\right\rfloor \sum_{k\mid m}\mu(k).}\)
又因为\(\mu\)的性质满足： \[ \sum_{k\mid m}\mu(k)= \begin{cases} 1,&m=1,\\ 0,&m>1. \end{cases} \]
因此上式只有 \(m=1\) 会留下：\(\displaystyle{\sum_{m\le n} m\left\lfloor\frac{n}{m}\right\rfloor \sum_{k\mid m}\mu(k)=1\cdot \left\lfloor\frac{n}{1}\right\rfloor\cdot 1n.}\)于是证得：
\[ \sum_{k=1}^{n} k\mu(k)D\left(\left\lfloor\frac{n}{k}\right\rfloor\right)=n. \]
把上式单独拎出 \(k=1\) 那一项，那么得到递推：
\[ D(n)=n-\sum_{k=2}^{n} k\mu(k)D\left(\left\lfloor\frac{n}{k}\right\rfloor\right). \]
其中区间求和的系数 \(\sum k\mu(k)\) 正好是 \(F(\cdot)\) 的差分。
不过，直接用\(\displaystyle{S(N)=\sum_{k=1}^{N} k\mu(k)D(\lfloor N/k\rfloor)^2}\)仍然计算量太大。设\(q=\lfloor\sqrt N\rfloor, w=\left\lfloor\dfrac{N}{q+1}\right\rfloor.\)
当 \(k\le w\) 时，\(\lfloor N/k\rfloor>q\)，此时 \(k\) 数量只有 \(O(\sqrt N)\)，可以直接算。当 \(k>w\) 时，\(\lfloor N/k\rfloor\le q\) 只有 \(O(\sqrt N)\) 种值。把所有 \(k\) 按 \(t=\lfloor N/k\rfloor\) 分组，则
\[ \sum_{\substack{k>w\\\lfloor N/k\rfloor=t}} k\mu(k)=F\left(\left\lfloor\frac{N}{t}\right\rfloor\right)-F\left(\left\lfloor\frac{N}{t+1}\right\rfloor\right). \]
最终得到经典分解：
\[ S(N)=\sum_{k=1}^{w} k\mu(k)D\left(\left\lfloor\frac{N}{k}\right\rfloor\right)^2 +\sum_{t=1}^{q} D(t)^2\left( F\left(\left\lfloor\frac{N}{t}\right\rfloor\right)- F\left(\left\lfloor\frac{N}{t+1}\right\rfloor\right) \right). \]
两段求和规模都是 \(O(\sqrt N)\)。
代码
1 |
|