Java 中的 LCM 总和

输入中会给出一个数字 n。我们的任务是找到从 1 到 n 的数字与数字 N 的 LCM 之和。换句话说，我们需要找到 lcm(1, n) + lcm(2, n) + lcm(3, n) + … + lcm(n, n) 的值。

示例 1

输入

int n = 6

输出 66

解释： lcm(1, 6) + lcm(2, 6) + lcm(3, 6) + lcm(4, 6) + lcm(5, 6) + lcm(6, 6) 的值为 6 + 6 + 6 + 12 + 30 + 6 = 66

示例 2

输入

int n = 3

输出 12

解释： lcm(1, 3) + lcm(2, 3) + lcm(3, 3) 的值为 3 + 6 + 3 = 12

简单方法

简单的方法是运行一个循环，并为每对数字计算 LCM。两个数字 p 和 q（假设）的 LCM 可以通过一个从 p 和 q 的最大值运行到 p x q 的循环来找到。在每次迭代中，我们需要检查循环变量所指向的值是否能被 p 和 q 整除。如果可以，我们可以使用 break 语句终止循环，该值就是 p 和 q 的 LCM。否则，循环将继续。请观察以下程序。

文件名： LCMSum.java

输出

The sum of LCM of numbers for the input number: 6 is 66
 
 
The sum of LCM of numbers for the input number: 3 is 12

复杂度分析： 存在一个从 1 到 n 的循环，需要 O(n) 的时间。在每次迭代中，我们调用 findLCM() 方法，该方法需要 O(a * n) 的时间，其中 a 从 1 运行到 n。因此，程序的总时间复杂度为 O(a * n²)，其中 n 是输入数字。程序空间复杂度为 O(1)。

现在，让我们通过一些优化来降低程序的时域复杂度。

方法：使用数学公式

两个自然数 p 和 q 的乘积的基本数学公式为：

p x q = HCF(p, q) x LCM(p, q)。因此，LCM(p, q) = (p x q) / HCF(p, q)。数字 p 和 q 已经已知。唯一需要找到的是 HCF（最高公因子）。HCF 可以通过一个从 min(p, q) 运行到 1 的循环来找到。如果循环变量所指向的值能同时整除两个数字，那么该值就是我们的 HCF，我们可以终止循环。之后，找到 LCM(p, q) 就很简单了。

找到 HCF 的另一种方法是欧几里得算法。我们将实现这两种方法来查找 HCF，并最终查找 LCM。请看以下程序。

文件名： LCMSum1.java

输出

The sum of LCM of numbers for the input number: 6 is 66
 
 
The sum of LCM of numbers for the input number: 3 is 12

复杂度分析： 第 60 行调用的方法决定了程序的时间复杂度。在程序中，调用了 findLCMUsingEuclidean() 方法（在第 60 行）。findLCMUsingEuclidean() 方法的时间复杂度为 O(log(min(a, n)))，其中 a 的范围从 1 到 n。另外，该方法被调用了 n 次。因此，程序的总时间复杂度为 O(n x log(min(a, n)))。如果我们使用 findLCMUsingMethod() 方法（在第 60 行），则该方法消耗的时间为 O(min(a, n))。程序的总时间复杂度为 O(n x log(min(a, n)))，其中 n 是输入数字。

方法：使用欧拉函数（欧拉函数）

我们将使用欧拉函数方法来解决问题。

输入为 'p' 的欧拉函数 Φ(p) 是列表中 {1, 2, 3, …, p} 中与 p 互质的数字的数量。换句话说，这些数字与 p 的 HCF（最高公因子）等于 1。下面给出了一些例子。

示例 1

Φ(1) = 1

gcd(1, 1) 为 1

示例 2

Φ(4) = 2

gcd(1, 4) 为 1，gcd(3, 4) 为 1

示例 3

Φ(7) = 6

gcd(1, 7) 为 1，gcd(2, 7) 为 1，

gcd(3, 7) 为 1，gcd(4, 7) 为 1

gcd(5, 7) 为 1，gcd(6, 7) 为 1

示例 4

Φ(8) = 4

gcd(1, 8) 为 1，gcd(3, 8) 为 1

gcd(5, 8) 为 1，gcd(7, 8) 为 1

要计算 Φ (p)，可以使用两种方法：

1) 使用 HCF

运行一个从 1 到 p 的循环，并检查每个数字与 p 的 HCF。每当 HCF 为 1 时，就可以递增该值。另一种方法是使用欧拉公式

2) 使用欧拉乘积公式

该公式表明 Φ(p) 的值等于 p 乘以 (1 - 1/t) 的乘积，其中 t 是 N 的所有素数因子。例如，

Φ(12) = 12 * (1 - 1 / 2) * (1 - 1 / 3) = 4。请注意，2 和 3 是 12 的素数因子。

在计算了每个数字的 ETF（欧拉函数）后，我们可以使用以下欧拉函数 LCM 和公式：

∑LCM(a, p) = ((∑(div * ETF(div)) + 1) * p) / 2

其中 ETF(div) 是 div 的欧拉函数，div 是 p 的除数集合。

让我们通过一个例子来验证。

示例

∑LCM(a, p) = LCM(1, 6) + LCM(2, 6) + LCM(3, 6) + LCM(4, 6) + LCM(5, 6) + LCM(6, 6) = 6 + 6 + 6 + 12 + 30 + 6 = 66，其中 a = 1，p = 6

现在，让我们使用欧拉函数：

6 的所有除数是：{1, 2, 3, 6}

因此，((1 x ETF(1) + 2 x ETF(2) + 3 x ETF(3) + 6 x ETF(6) + 1) * 6) / 2 = ((1 + 2 + 6 + 12 + 1) x 6) / 2 = 132 / 2 = 66

我们得到了相同的结果。现在是实现部分。

文件名： LCMSum2.java

输出

The sum of LCM of numbers for the input number: 6 is 66
 
 
The sum of LCM of numbers for the input number: 3 is 12

复杂度分析： 查找数字 n 的因子需要 log(log(n)) 的时间，并且我们正在查找 n 个数字的因子。因此，程序的总时间复杂度为 O(n x log(log(n)))，其中 n 是输入数字。