找到可从1到N之间的所有数字整除的最小数字,剩余数= 0

Question

找到可从1到N的所有数字整除的最小数字,不留任何余数.由于数字可能非常大,我们采用模数1000000007的答案.

我认为可以被1到N的所有数字整除的最小数字是LCM(1..N).

示例:对于N = 5,该最小数字将为60.

因为60是可被所有数字形式整除的最小数字(1-5).

但是由于一些奇怪的原因,它给了我大的N(1000)的错误答案,等等.这里可能导致错误的是什么,我的登录是否正确？

这是我试图实施的内容.

#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

问题是当你计算LCM时,你使用除法,

和

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

例如 (10/5/2) % 2 != ((10/5)%2)/2)%2

您应该使用模块化逆来计算它.

关于模逆的一些解释.

如果我们有:

(a*b) % m = 1,然后b是模块化逆a,作为 b % m = (1/a) % m.

因此,如果我们需要计算(x/a) % m,我们可以使它成为(x * b ) %m.

我们知道(A*B*C)% m = ((A * B) % m)*C)% m,因此,在您的情况下,模块化逆会派上用场.