丢番图倒数的一道变种题

2019-08-06 本文已影响0人 yo1995

xyz.png

前言

在虎扑和各种论坛上经常有小学奥数题出现。每次遇到这样的题都会被蜜罐——自己总抱有一种“前事不忘后事之师”的“敝帚自珍”、收破烂的心态，总是不肯承认自己不再擅长小时候那些初等数学中比较复杂的问题。有时候，看到诸如“求阴影面积”的题还是会去做辅助线建系用初等方法费劲吧啦地求解，解出后却有种怅然若失、捶胸顿足之感——又被网络上的“时间小偷”给盘了！

今天又看到一个这种问题，浪费了将近一个半小时才彻底搞明白前因后果。真是后悔啊……

起手

projecteuler 108
projecteuler 110
史上最贱的数学题

fruit.jpg

丢番图倒数、丢番图方程是一个很经典的问题。但其变种却引申出了数学中许多非常深刻的理论。这道题化简后得到是一个二次的问题：

求解 $y=n+\frac{n^2}{(x-n)}$ 对于不同 n 时， $(x, y)$ 解的个数。

由于 x、y、n 分别都是正整数，且题目存在隐含条件 $x\leq y$ 。因此，问题便简化为求解一个形如 $n^2$ 的整数有多少个因数了。

编程 1

上面的问题很简单，也比较直观。

对于任意正整数 n，可以通过短除法求出其质因数分解。如果预先有质数表（筛法）的话效率更高。没有质数表对于较小的分解也问题不大。

def prime_factors(n: int):
    results = []
    while n % 2 == 0:
        results.append(2)
        n = n // 2
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        while n % i == 0:
            results.append(i)
            n = n // i
    if n > 2:
        results.append(n)
    return results

如想得到所有因子，可以算出因子个数后循环生成得到。

因此，对于给定任意 n，求其有多少个因子/多少组 $(x, y)$ 解的问题，求解非常简单。

然而，这个问题绝非上述分析那么简单。难点在于如何满足“恰好”这个条件。

分析

因子的数量

相对于 projecteuler 110 求解 4M 个解时对应的 n 的大小，本题有异曲同工之妙，但难度稍低。目前，我们能够得到任何可以计算的正整数 n 对应的解的个数，那如何找到特定解的个数对应的最小的 n 值呢？

继续分析。首先，比较好理解的一点：解的个数是 $n^2$ 因子个数加一除以二。因为 n 本身是 $n^2$ 的因子，但只计入一次；而其他解则为因子的对称配对，又由于 $x\leq y$ ，故可以通过因子个数得到解的个数，反之亦然。

因此，对于解的个数分别为 100、1000、1000000 (1M)的三个问题，我们需要得到的因子个数则为 199、1999、1999999 (2M-1)。通过 O(1) 素数查表得知，199、1999 为素数，而 1999999 非素数。通过质因数分解函数求得 1999999 = 17 × 71 × 1657。此时，所需条件都已求得