先找规律后推公式，自然数幂和公式

摘要: 找规律，推公式

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

各位好，本文我们看一个值域二分的问题。假设有一个 $f(x)$，我们想知道使得 $f(x) \geq M$ 成立的最小的 $x$ 是多少。如果 $f(x)$ 是单调的，则可以考虑值域二分，整体思路是在值域范围 $[left, right]$ 中，检查 $f(mid)$ 的值，由 $f(x)$ 的单调性可以根据检查结果来调整 $left$ 和 $right$。

本文的问题的难点是 $f(x)$ 涉及到一些找规律以及公式推导。

题目

给你一个用无限二维网格表示的花园，每一个 整数坐标处都有一棵苹果树。整数坐标 $(i, j)$ 处的苹果树有 $|i| + |j|$ 个苹果。

你将会买下正中心坐标是 $(0, 0)$ 的一块 正方形土地 ，且每条边都与两条坐标轴之一平行。

给你一个整数 neededApples ，请你返回土地的 最小周长 ，使得 至少 有 neededApples 个苹果在土地 里面或者边缘上。

示例 1：
输入：neededApples = 1
输出：8
解释：边长长度为 1 的正方形不包含任何苹果。
但是边长为 2 的正方形包含 12 个苹果（如上图所示）。
周长为 2 * 4 = 8 。

示例 2：
输入：neededApples = 13
输出：16

示例 3：
输入：neededApples = 1000000000
输出：5040

提示：

1 <= neededApples <= 1e15

题解

算法：值域二分 + 数学算法

记 $g(i)$ 为边长为 $i$ 的正方形，内部以及边上的苹果总数。当 $i$ 变大时，正方形变大，有可能会引入新增的苹果，而此前已经在内部的苹果不会失去，因此 $g(i)$ 只会不变或变大，而不会变小。这样我们就可以通过值域二分来找到最小的 $i$，使得 $g(i) \geq M$，$4i$ 即为最终答案。

现在的难点是找到 $g(i)$ 的公式，需要通过试验 $i$ 比较小的情况找规律，然后猜出公式的大致形式，然后再进行推导，给出最终的公式。

由于正方形中心固定，因此一个自然的想法是将正方形从内向外分为各个层，第 $i$ 层为边长为 $i$ 的正方形。然后单独计数边长为 $i$ 的正方形边上的苹果数，记其为 $f(i)$，于是

$$g(i) = \sum\limits_{j=1}\limits^{i}f(j)$$

下面考察 $f(i)$。首先如果 $i = 2k - 1, k=1,2,\cdots$，则这一层正方形的边不在整数点上，$f(i) = 0$。当 $i = 2k$ 时，正方形的边可以分成 4 份，每份是对称的，因此只考察一份即可。考察右边的那条边对应的那一份，涉及到的若干点为：

$$(k, -k), (k, -k+1), \cdots, (k, 0), \cdots, (k, k-1)$$

各个点的苹果数为：

$$2k, 2k-1, \cdots, k, \cdots, 2k-1$$

下面是 $i = 6, k = 3$ 的示意图：

于是当 $i = 2k$ 时：

$$f(i) = f(2k) = 4 (\sum\limits_{j=k+1}\limits^{2k}j + \sum\limits_{j=k}\limits^{2k-1}j) = 12k^{2}$$

于是可以写出 $g(i)$ 的公式，记 $n = \left\lfloor\frac{i}{2}\right\rfloor$，有：

$$g(i) = \sum\limits_{k=1}\limits^{n}f(2k) = \sum\limits_{k=1}\limits^{n}12k^{2} = 2n(n+1)(2n+1)$$

自然数幂和公式

自然数幂和指的是 $1^{m} + 2^{m} + \cdots, n^{m}$ 这个求和问题，现代的主流解法有伯努利数和母函数这两种。当 $m$ 较小的时候，有初等方法可以解决，历史上很早的时候就得出了公式。只是 1834 年才由雅可比给出了 $m=2, 3$ 时的证明。

本题用到了 $m=2$ 时的公式：

$$\sum\limits_{i=1}\limits^{n}i^{2} = \frac{1}{6}n(n+1)(2n+1)$$

代码 (Python)

def g(i):
    n = i // 2
    return 2 * n * (n + 1) * (2 * n + 1)

def check(i, neededApples):
    # 边长为 i 的矩形，苹果数量是否大于等于 neededApples
    return g(i) >= neededApples

class Solution:
    def minimumPerimeter(self, neededApples: int) -> int:
        left = 1
        right = int(1e15)
        while left < right:
            mid = (left + right) // 2
            if check(mid, neededApples):
                right = mid
            else:
                left = mid + 1
        return left * 4

---