3

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; 
}
Yuchen
  • 30,852
  • 26
  • 164
  • 234
nitte93
  • 1,820
  • 3
  • 26
  • 42
  • Looks like C++, but I could be wrong. Please tag questions with the language you are using. – Felix Kling Jun 07 '15 at 18:10
  • Should this be post to [code review](http://codereview.stackexchange.com)? – Yuchen Jun 07 '15 at 18:12
  • 4
    @Yuchen: No. Code Review is for asking for improvements to working code (or apparently working code). – Benjamin Lindley Jun 07 '15 at 18:13
  • I think this too might be useful for this question, http://stackoverflow.com/questions/24574299/lcm-of-n-numbers-modulo-1000000007 – nitte93 Jun 07 '15 at 19:02
  • Seems like this question has reappeared a few times: http://stackoverflow.com/questions/30543106/how-to-calculate-least-common-multiple-of-1-2-3-n/30544439#30544439 – Edward Doolittle Jun 07 '15 at 19:16
  • I think none of the answers given before (in all questions) really solves the problem in a scalable way. Posted an answer below. – Juan Lopes Jun 07 '15 at 20:50

2 Answers2

6

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.

Pham Trung
  • 11,204
  • 2
  • 24
  • 43
1

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;
}
Juan Lopes
  • 10,143
  • 2
  • 25
  • 44