LOJ 6165 一道水题

题目链接

把每个数唯一分解\(n=\prod p-i^{e-i}\)，显然最终答案的每个质因数指数都不小于\([1,n]\)的每个数分解的指数。
但是这样是\(\mathjaxcal{O}(n\sqrt{n})\)的。

我们只用关心每个质数最大的\(e-i\)是多少。
显然是其他数都是\(1\)的时候，不断用\(n\)除就能得到\(e-i\)的值。

话说我怎么要用\(bitset\)才能过这道题啊...

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e8 + 4, MOD = 100000007;
int P[6200000], tot, n;
bitset<N> vis;

ll qaq = 1;

void init(int n) {
	for (int i = 2; i <= n; i++) {
		if (!vis[i]) P[++tot] = i;
		for (int j = 1; j <= tot && P[j] * i <= n; j++) {
			vis[i * P[j]] = 1;
			if (i % P[j] == 0) break;
		}
	}
} 

int main() {
    scanf("%d", &n);
	init(n);
	for (int i = 1; i <= tot; i++) {
        int d = n, p = P[i];
		while (d / p) d /= p, qaq = qaq * 1ll * p % MOD;
	}
	printf("%lld\n", qaq);
	return 0;
}