ProjectEuler_做题记录

简单记录一下。

problem 441 The inverse summation of coprime couples

神仙题。考虑答案为：

$$\begin{array}{c} S(n) & = & \sum_{i = 1} ^ n \sum_{p = 1} ^ i \sum_{q = p + 1} ^ i \frac {1}{pq}[p + q \geq i][gcd(p, q) = 1] \\ & = & \sum_{i = 1} ^ n \sum_{p = 1} ^ i \sum_{q = p + 1} ^ i \frac {1}{pq}[p + q \geq i] \sum_{d|gcd(p, q)} \mu(d) \\ & = & \sum_{i = 1} ^ n \sum_{d = 1} ^ n \mu(d) \sum_{p = 1} ^ {\lfloor i/d \rfloor} \sum_{q = 1} ^ {\lfloor i/d \rfloor} \frac {1}{pqd ^ 2}[pd + qd \geq i]\\ & = & \sum_{i = 1} ^ n \sum_{d = 1} ^ n \frac {\mu(d)}{d ^ 2} \sum_{p = 1} ^ {\lfloor i/d \rfloor} \sum_{q = 1} ^ {\lfloor i/d \rfloor} \frac {1}{pq}[p + q \geq \lfloor i/d \rfloor] \\ & - & \frac {1}{pq}[p + q = \lfloor i/d \rfloor][i \ mod \ d = 0] \\ \end{array}$$
我们考虑构造三个函数：
$$\begin{array}{c} F(n) & = & \sum_{i = 1} ^ n \frac {1}{i} \\ G(n) & = & \sum_{i = 1} ^ n \sum_{j = i + 1} ^ n \frac {1}{ij} [i + j = n] \\ T(n) & = & \sum_{i = 1} ^ n \sum_{j = i + 1} ^ n \frac {1}{ij} [i + j \geq n] \\ \end{array}$$
事实上，我们可以解出这三个函数的递归式，然后做到$O(N)$预处理。
然后最后的式子会变成：
$$S(n) = \sum_{d = 1} ^ n \frac {\mu(d)}{d ^ 2} \sum_{i = d} ^ n(T(\lfloor i/d \rfloor) - G(\lfloor i/d \rfloor)[i \ mod \ d \neq 0])$$
然后就可以根据调和级数做到$O(n \ lnn)$。

problem 530 GCD of Divisors

由于直接化简比较困难，考虑将整个答案一起化简：

$$\begin{array}{c} ans & = & \sum_{i = 1} ^ n \sum_{d \mid i} gcd(d, \frac {i}{d}) \\ & = & \sum_{g = 1} ^ n g \sum_{i = 1} ^ {n} \sum_{d \mid i} [gcd(d, \frac {i}{d}) = g]（先枚举gcd的套路）\\ & = & \sum_{g = 1} ^ n g \sum_{i = 1} ^ {\lfloor n/g^2 \rfloor} \sum_{d \mid i} [gcd(d, \frac {i}{d}) = 1]（设i = \frac {i}{g ^ 2}, d = \frac {d}{g}）\\ & = & \sum_{g = 1} ^ n g \sum_{i = 1} ^ {\lfloor n/g^2 \rfloor} \sum_{d \mid i} \sum_{t \mid gcd(d, \frac {i}{d})} \mu(t) \\ & = & \sum_{g = 1} ^ n g \sum_{t = 1} ^ n \mu(t) \sum_{i = 1} ^ {\lfloor n/(gt) ^ 2 \rfloor} \sum_{d \mid i} 1 （设i = \frac {i}{t ^ 2}, d = \frac {d}{t}，也是套路）\\ & = & \sum_{g = 1} ^ n g \sum_{t = 1} ^ n \mu(t) \sum_{i = 1} ^ {\lfloor n/(gt) ^ 2 \rfloor} \sigma_0(i)（\sigma_0(i)表示i的因子个数）\\ &!&（下一步是个新套路，构造\phi的卷积形式\phi = \mu * 1） \\ & = & \sum_{k = 1} ^ {\sqrt n} \sum_{g \mid k} g\mu(\frac {k}{g}) \sum_{i = 1} ^ {\lfloor n/k ^ 2 \rfloor} \sigma_0(i)（k = gt，注意k的取值只需要到\sqrt n）\\ & = & \sum_{k = 1} ^ {\sqrt n} \phi(k) \sum_{i = 1} ^ {\lfloor n/k ^ 2 \rfloor} \sigma_0(i)\\ &!& （最后套用\sum_{i = 1} ^ {m} \sigma_0(i) = \sum_{i = 1} ^ m \lfloor \frac {m}{i} \rfloor）\\ & = & \sum_{k = 1} ^ {\sqrt n} \phi(k) \sum_{i = 1} ^ {\lfloor n/k ^ 2 \rfloor} \lfloor \frac {\lfloor n/k ^ 2 \rfloor}{i} \rfloor \\ \end{array}$$
对后面部分使用除法分块，复杂度就是$\sum_{i = 1} ^ {\sqrt n} O(\sqrt \frac {n}{i ^ 2}) = \sum_{i = 1} ^ {\sqrt n} O(\frac {\sqrt n}{i}) = O(\sqrt n \ ln \sqrt n)$

problem 233 Lattice points on a circle

首先要知道一个结论——费马平方和定理。具体的证明网上很多，就不讲了。其实是挺妙的。费马平方和定理：如果一个质数能表示成4n+1的形式，这个数一定能分解成两个完全平方数的和。
事实上，这个分解是唯一的。这可能要用到环论的知识。

首先一点，很容易证明对于一个数x，满足$f(2x)=f(x)$。
这样，对于所有情况，都可以先变成n是偶数的情况，然后将圆心移动至原点处，对答案也是没有影响的。
然后对于任意一个数n，将它不断除以2，知道它是奇数，这段时间内答案都是不变的。因为对于一个偶数n，满足$x^2+y^2=n^2$的x，y只有可能都是偶数，这样x/2, y/2就可以作为n/2的一组合法解。这样我们只需要考虑n是所有奇数的情况了。

然后就发现不会做了。发现有点不对劲。

有一个解法好像很简明，用到了高斯素数的理论。
答案其实等于范数为$N^2$的高斯整数的个数。
高斯整数公式（$g(n)$表示范数为$n$的高斯整数个数）：

$$g(n) = 4 \prod_{j = 1}^s e_j + 1$$
其中，将n因子分解有 $$n = 2^e_0 \prod_{k = 1}^s p_k^{e_k} \prod_{k = s + 1}^{s + t} q_k^{e_k}$$
而$p_k$是模4余1的质数，$q_k$是模4余3的质数。
则$f(N)$为 $$g(N^2) = 4 \prod_{j = 1}^s 2e_j + 1 = 420（根据已知）= 4 * 3 * 5 * 7$$
则指数$e_j$有这么几种情况：
$$e1=10, e2=2; \\ e1=7, e2=3; \\ e1=3, e2=2, e3=1.\\ $$
然后暴枚所有情况即可，即在满足上面$e_j$的某种情况时，再乘上2的几次幂，还有一些模4余3的质数的几次幂，小于N的情况（状态数非常少，可以很快跑出来）。