LightOj 1289 - LCM from 1 to n（LCM + 素数）

题目链接：http://lightoj.com/volume_showproblem.php?problem=1289

题意：求LCM(1, 2, 3, ... , n)%(1<<32), (1<n<=1e8);

LCM(1, 2, 3, ... , n) = n以内所有素数的最高次幂之积，例如15: 2³*3²*5*7*11*13 = 36360360;

为了防止TLE所以，要有一个数组表示前缀积，但是直接开LL会MLE是，因为有个%1<<32刚好是unsigned int之内，可以开int的数组；

关于求1e8内的素数表，用bool类型也会MLE的，所以可以使用bitset类型;

#include <stdio.h>

#include <string.h>

#include <math.h>

#include <algorithm>

#include <bitset>

#include <iostream>

#include <time.h>

typedef long long LL;

using namespace std;

const int N = 1e8+;

const double eps = 1e-;

const int INF = 0x3f3f3f3f;

const LL mod = (1ll<<);

int k, p[];

unsigned int  Mul[];

bitset<N> f;

void Init()

{

    f.reset();

    for(int i=; i<N; i++)

    {

        if(f[i]) continue;

        p[k++] = i;

        for(int j=i+i; j<N; j+=i)

            f[j] = ;

    }

}

int main()

{

    int T, t = ;

    scanf("%d", &T);

    Init();

    Mul[] = p[];

    for(int i=; i<k; i++)

        Mul[i] = Mul[i-]*p[i];

    while(T --)

    {

        int n;

        scanf("%d", &n);

        int pos = upper_bound(p, p+k, n)-p - ;

        LL ans = Mul[pos];

        for(int i=; i<k && (LL)p[i]*p[i]<=n; i++)

        {

            LL num = ;

            while(num <= n)

                num *= p[i];

            if(num%(p[i]*p[i]) == ) num /= (p[i]*p[i]);

            ans = ans*num%mod;

        }

        printf("Case %d: %lld\n", t++, ans);

    }

    return ;

}

还有一种比较快一点的方法：

#include <stdio.h>

#include <string.h>

#include <math.h>

#include <algorithm>

#include <bitset>

#include <iostream>

#include <time.h>

typedef long long LL;

using namespace std;

const int N = 1e8+;

const double eps = 1e-;

const int INF = 0x3f3f3f3f;

const LL mod = (1ll<<);

int k = , p[], f[N/+];

unsigned int  Mul[];

void Init()

{

    p[k++] = ;

    for(int i=; i<N; i+=)

    {

        if(f[i/]&(<<((i/)%)))

            continue;

        p[k++] = i;

        for(int j=*i; j<N; j+=*i)

            f[j/] |= (<<((j/)%));

    }

    ///printf("%d\n", k);

}

int main()

{

    int T, t = ;

    scanf("%d", &T);

    Init();

    Mul[] = p[];

    for(int i=; i<k; i++)

        Mul[i] = Mul[i-]*p[i];

    while(T --)

    {

        int n;

        scanf("%d", &n);

        int pos = upper_bound(p, p+k, n)-p - ;

        LL ans = Mul[pos];

        for(int i=; i<k && (LL)p[i]*p[i]<=n; i++)

        {

            LL num = ;

            while(num <= n)

                num *= p[i];

            if(num%(p[i]*p[i]) == ) num /= (p[i]*p[i]);

            ans = ans*num%mod;

        }

        printf("Case %d: %lld\n", t++, ans);

    }

    return ;

}

巴特西

LightOj 1289 - LCM from 1 to n（LCM + 素数）

最新文章

热门文章