n个数字的LCM模1000000007 [英] LCM of n numbers modulo 1000000007

问题描述

我必须找到n个数的LCM MODULO 10 ^ 9 + 7.我的方法是找到两个数的LCM，然后对其进行MOD.然后取下一个元素的LCM和从上一次迭代获得的答案并将其MOD.对所有元素都执行此操作吗?

I have to find LCM of n numbers MODULO 10^9+7.My approach is find LCM of two numbers and then MOD them.Then take the LCM of next element and the answer obtained from the previous iteration and MOD them.Do this for all elements.Is it wrong ?

推荐答案

是的，这是错误的.我一直在研究类似的问题.

Yes, it is wrong. I have been working on a similar problem.

您必须熟悉MOD的以下属性:

You must be familiar with the following property of MOD:

属性1:(a * b * c * d ... * p * q)％MOD =(a％MOD)(b％MOD)(c％MOD) ..... (q％MOD);

PROPERTY 1: (a*b*c*d...*p*q) % MOD = (a%MOD)(b%MOD)(c%MOD).....(q%MOD);

，但LCM并非如此.

but this is not the case with LCM.

LCM(a，b)= a * b/GCD(a，b).

LCM(a,b)=a*b/GCD(a,b).

LCM(LCM(a，b)，c)= LCM(a，b)* c/GCD(LCM(a，b)，c).

LCM(LCM(a,b),c)=LCM(a,b)*c/GCD(LCM(a,b),c).

只要LCM大于MOD，上述属性就会被破坏.您必须尝试仅根据分子中不同数字的乘积来查找LCM.

Whenever LCM becomes greater than the MOD, the above mentioned property gets destroyed. You must try to find LCM in terms of products of different numbers in numerator only.

这可以通过分解所有数字并保留各种因素的最高功效记录来完成.

This can be done by factorizing all the numbers and keeping the record of highest powers of various factors.

LCM =(2 ^ a)(3 ^ b)....现在，您可以轻松地迭代乘以它们，并通过使用属性1将限制保持在MOD下.

LCM = (2^a)(3^b).... Now you can easily multiply them iteratively and also keep the limit under MOD by using property 1.

这篇关于n个数字的LCM模1000000007的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！