如何计算{1,2,3,..........,n}的最小公倍数？

Question

如何以最快的方式找到{1,2,...,n}的LCM,其中0 < n < 10001.一种方法是计算n!/ gcd(1,2,.....,n)但这可能很慢,因为测试用例的数量是t <501,输出应该是LCM(n!)%1000000007

代码相同的是:

#include<bits/stdc++.h>
using namespace std;
#define p 1000000007;
int fact[10001] = {1};
int gcd[10001] = {1};

int main()
{
    int i, j;
    for( i = 2;i < 10001; i++){
        fact[i] = ( i * fact[i-1]) % p;
    }
    for(i=2 ;i < 10001; i++){
        gcd[i] =__gcd( gcd[i-1], i );
    }

    int t;
    cin >> t;

    while( t-- ) {
        int n;
        cin >> n;
        int res = ( fact[n] / gcd[n] );
        cout << res << endl;
    }

    return 0;
}

但是这段代码表现不佳.为什么？

Answer 1

我会以完全不同的方式计算它：{1,...,n} 的 LCM 是所有素数 p[i]<=n 的乘积，每个素数的幂底数(log(n)/log(p[i) ]））。该乘积可被 n 以内的所有数字整除，并且这是最小的此类数字。你的主要麻烦是计算素数表。