Find the smallest number that is divisible by all the number between 1 to N, Remainder = 0

Question

Find the smallest number which is divisible by all numbers from 1 to N, without leaving any remainder. As number can be very large we take the answer modulo 1000000007.

I think the smallest number that would be divisible by all the number from 1 to N,would be LCM(1..N).

Example: for N = 5, that smallest number would be 60.

As 60 is the smallest number divisible by all the number form (1-5).

But for some strange reason its giving me wrong answer for large N(1000), etc. What can cause the possible error here, is my login correct here?

Here's what i tried to Implement.

#include <iostream>
#include <vector>
using namespace std;

vector<long long> lcmArr;
const long long mod = 1000000007;

long long gcd(long long a, long long b){
    if(b == 0) 
    {
        return a;
    }

    return gcd(b, a%b);
}

long long lcmFumction(long long  a, long long  b)
{
    return (a*b)/gcd(a,b);  
}

int main() {
    lcmArr.clear();lcmArr.resize(1002);
    lcmArr[0] =0; lcmArr[1] = 1;
    for(int i =2; i <=1000; i++){
        lcmArr[i] = lcmFumction(lcmArr[i-1], i)%mod;
            //cout<<lcmArr[i-1]<<" ";
    }

    int T;
    cin >> T;
    while(T--) {
        int N;
        cin>>N;
        cout<<lcmArr[N]<<"\n";
    }
    return 0; 
}

Answer 1

The problem is when you calculate LCM, you use division,

And

((A/B)/C) mod M != (((A/B) mod M)/C)mod M

For example (10/5/2) % 2 != ((10/5)%2)/2)%2

You should use modular inverse to calculate that.

Some explanation about modular inverse.

If we have:

(a*b) % m = 1, then b is modular inverse of a, as b % m = (1/a) % m.

Thus, if we need to calculate (x/a) % m, we can make it become (x * b ) %m.

And we know that (A*B*C)% m = ((A * B) % m)*C)% m, so, in your case, modular inverse will come in handy.

Answer 2

I know the answer above has already been accepted, but I think that won't be enough to solve your problem. The problem lies in the fact that the first modular LCM will take away all divisors you need to check in subsequent GCD calls, so the answer will still be wrong.

One possible solution is to keep an array of factors for the answer. Each factor will be each number from 1..N, divided by GCD(number, [all previous numbers]). For this to work, you have to code a special GCD that computes the result between a single number and an array of factors. This C++ code shows how this 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;
}