K Simple question （第十届山东理工大学ACM网络编程擂台赛正式赛）

题解：素数筛+唯一分解定理

可以把素数筛那部分放到while之外，减小时间复杂度。

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <stdbool.h>

#include <assert.h>

const int maxn = 110000005;

const int mod = 100000007;

const int N = 60000008;

int prime[N];

bool vis[maxn];

int main()

{

    int n;

    while(~scanf("%d",&n)){

    assert(1 <= n && n <= 100000000);

    long long ans = 1;

    int cnt=0;

    memset(vis,false, sizeof(vis));

    for (int i = 2; i <= n; i++)

    {

        if (!vis[i])

        {

            prime[cnt++] = i;

            for (long long j = i; j <= n; j *= i)

            {

                ans = ans * i % mod;

            }

        }

        for (int j = 0; j < cnt; j++)

        {

            long long x = i * prime[j];

            if (x > n)break;

            vis[x] = true;

            if (i%prime[j] == 0)break;

        }

    }

    printf("%lld\n",ans);

    }

return 0;

}

巴特西

K Simple question （第十届山东理工大学ACM网络编程擂台赛正式赛）

最新文章

热门文章

巴特西

K Simple question （第十届山东理工大学ACM网络编程擂台赛 正式赛）

最新文章

热门文章

K Simple question （第十届山东理工大学ACM网络编程擂台赛正式赛）