c++ - 求能被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

你应该使用 modular inverse来计算。

关于模逆的一些解释。

如果我们有:

(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，因此，在您的情况下，模逆将出现方便。