求可被1到N之间的所有数字整除的最小数，余数=0

Question

求可被1到N的所有数整除的最小数，不留余数。由于数字可能非常大，我们取模100000007的答案。

我认为可以被从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会带走你在后续GCD调用中检查所需的所有因子，所以答案仍然是错误的。

一种可能的解决方案是为答案保留一系列因子。每个因子将是1中的每个数字。。N、 除以GCD（数字，[所有以前的数字]）。为此，您必须编写一个特殊的GCD，用于计算单个数字和因子数组之间的结果。此C代码显示了这将如何工作：

#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;
}

Answer 2

问题是当计算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，所以，在你的例子中，模逆会派上用场。