LibieOJ 6165 一道水题 （线性筛）

题目链接 LOJ6165

题目意思其实就是求LCM(1, 2, 3, ..., n)

直接用线性筛求出1到1e8之间的所有质数

然后对于每个质数p，他对答案的贡献为$p^{i}$ 其中$p^{i}$小于等于n且要最大。

c数组可能很大，所以我开了bitset...

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)
#define dec(i, a, b)	for (int i(a); i >= (b); --i)

typedef long long LL;

const int N  =  6170736;
const int M  = 100000002;
const LL mod = 100000007;

int n, pn;
int p[N];
bitset <M> c;
LL ans = 1LL;
int v;

int main(){

	scanf("%d", &n);
	pn = 0;
	rep(i, 2, n){
		if (!c[i]){
			p[++pn] = i;
			for (LL s = i; s <= n; s *= i)
				ans = ans * i % mod;
		}

		rep(j, 1, pn){
			v = i * p[j];
			if (v > n) break;
			c[v] = 1;
			if (i % p[j] == 0) break;
		}
	}
	printf("%lld
", ans);
	return 0;
}