小编DCo*_*der的帖子

如何以最快的方式找到{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 phi (int n) {
    int result = n;
    for (int i=2; i*i<=n; ++i)
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
    if (n > 1)
        result -= result / n;
    return result;
}

我看到上面的Euler phi函数的实现是O(sqrt n).我没有得到i*i<=n在for循环中使用的事实并且需要改变.n据说它可以在更小的时间内完成O. (sqrt n)怎么样？链接(俄语)