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

问题描述

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

How to find LCM of {1, 2, ..., n} where 0 < n < 10001 in fastest possible way. The one way is to calculate n! / gcd (1,2,.....,n) but this can be slow as number of testcases are t < 501 and the output should be 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;
}

但是此代码的效果不佳.为什么?

But this code is not performing as well. Why?

推荐答案

我将以完全不同的方式进行计算:{1，...，n}的LCM是所有素数p [i]<的乘积. = n，每个在功率层中(log(n)/log(p [i])).该乘积最多可被n整除，这是最小的此类数.您的主要麻烦是然后要计算素数表.

I would calculate this in completely different way: the LCM of {1,...,n} is a product of all primes p[i]<=n, each in power floor(log(n)/log(p[i])). This product is divisible by all numbers up to n, and this is the least such number. Your main trouble is to calculate table of primes then.

这篇关于如何计算{1,2,3，..........，n}的最小公倍数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！