algorithm - 最小公倍数模一些 p

Question

假设我们必须找到数字 lcm 的最小公倍数 ( a1 ... an ) .

为了解决这个问题，我们可以使用递归解决方案:

lcm(a, b) = (a * b) / gcd(a, b)其中 gcd(a, b)表示 a 的最大公约数 |和 b

lcm(a1 ... an) = lcm(a1, lcm(a2 ... an))

问题是:

如果我们对 lcm(a1 ... an) mod p 感兴趣怎么办？其中 p是一些质数数。 lcm(a1 ... an)太大而无法存储在 int 中.

Answer 1

之前有一些关于该主题的问题:

• LCM of n numbers modulo 1000000007
• Calculate LCM of N numbers modulo 1000000007

你有两个选择:

---

选项 1:一般趋势似乎是，如果您的值对于 unsigned long long int 仍然太长，那么您需要对数字进行质数分解。取每个数字 a_i 并将其分解为质因数 (2^r)(3^s)(5^t)...要获得 LCM，您只需为每个质因数取最大指数即可。

比如15和18的LCM可以这样做:

15 = (2⁰)(3¹)(5¹)

18 = (2¹)(3²)(5⁰)

2的最大指数为1，3的最大指数为2，5的最大指数为1。因此，LCM(15,18) = (2¹)(3 ²)(5¹) = 2(9)(5) = 90。但是，我们可以在这个乘法步骤中执行模运算，因为 ab (mod n ) = ((a (mod n)) (b (mod n))) mod n。因此，只需在每一步乘法后取模即可。

---

选项 2:此选项涉及找到 _i 子集的 GCD。将其保存为 g₀ 并将所有为 g₀ 的倍数的 a_i 除以 g₀。找到新 a_i 的另一个子集的 GCD 并将其保存在 g₁。同样，将所有作为 g₁ 的倍数的 a_i 除以 g₁。重复此操作，直到 a_i 的所有子集的 GCD 为 1。然后您只需根据您的 mod 规则将所有 a_i 和 g_i 相乘。例如:

液晶模组(15,18,10)

GCD(15,10) = 5 所以 g₀ = 5 和 a = (3,18,2)。

GCD(3,18) = 3 所以 g₁ = 3 和 a = (1,6,2)。

GCD(6,2) = 2 所以 g₂ = 2 和 a = (1,3,1)。此时，a 的任何子集的 GCD 都将为 1，我们就完成了。

将它们全部放回一起 LCM(15,18,10) = 5(3)(2)(1)(3)(1) = 90