LCM of n numbers modulo 1000000007
Yes, it’s wrong. I am working on a similar problem.
You should be familiar with the following MOD property:
PROPERTY 1: (a * b * c * d ... * p * q)% MOD = (a% MOD) (b% MOD) (c% MOD) ..... (q% MOD);
but this is not the case for LCM.
LCM (a, b) = A * B / GCD (a, b).
LCM (LCM (a, b), c) = LCM (a, b) * c / gcd (LCM (a, b), c).
Whenever LCM becomes larger than MOD, the above property is destroyed. You should try to find LCM in terms of products of a different number in the numerator only.
This can be done by factoring all the numbers and keeping a record of the higher powers of the various factors.
LCM = (2 ^ a) (3 ^ b) .... Now you can easily multiply them iteratively and also store the limit in MOD with property 1.
source to share
Just for future reference, here's a C ++ implementation that doesn't use simple factorization.
One possible solution is to keep many factors to answer. Each coefficient will be each number from 1..N divided by GCD (number, [all previous numbers]). For this to work, you need to code a special GCD that computes the result between a single number and an array of factors. This C ++ code shows how it would work:
#include <iostream>
#include <vector>
#define lli long long int
using namespace std;
vector<lli> T;
lli gcd(lli a, lli b) {
if(b == 0)
return a;
return gcd(b, a%b);
}
lli gcd_vector(vector<lli>& a, lli b) {
lli ma = 1;
for(int i=0; i<T.size(); i++)
ma = ma*T[i]%b;
return gcd(b, ma);
}
int main() {
lli answer = 1;
for(int i=1; i<=1000; i++) {
lli factor = i/gcd_vector(T, i);
T.push_back(factor);
answer = (answer*factor)%1000000007;
}
cout << answer << endl;
}
source to share