Find the smallest number that is divisible by everything from 1 to N, Remainder = 0
Find the smallest number that is divisible by all numbers from 1 to N, leaving no remainder. Since the number can be very large, we accept the answer modulo 1000000007.
I think the smallest number that will be divisible by the whole number from 1 to N would be LCM (1..N).
Example: for N = 5 this smallest number would be 60.
Because 60 is the smallest divisible number (1-5).
But for some strange reason it gives me the wrong answer for large N (1000) etc. What could lead to a possible error here, my login is here?
Here is what I was trying 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;
}
source to share
The problem is when you calculate LCM you are using 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 have to use modular inverse to calculate this.
Some explanations for the modular inverse.
If we have:
(a*b) % m = 1
then b
is modular, inverse to a
like b % m = (1/a) % m
.
That way, if we need to compute (x/a) % m
, we can do it (x * b ) %m
.
And we know that (A*B*C)% m = ((A * B) % m)*C)% m
, so in your case, a modular reverse will come in handy.
source to share
I know the answer above is already accepted, but I think it won't be enough to solve your problem. The problem is that the first modular LCM will remove any divisors you need to check in subsequent calls to GCD, so the answer will still be wrong.
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]). To do this, you need to code a special GCD that computes the result between one number and many 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