题目

分析

1. 根小于等于n/2
2. 当p>=3时，p^k*2 <= n
3. 当p==2时，p^k*3 <= n

代码

#include<bits/stdc++.h>
using namespace std;
#define MAX_N 80000001
const long long mod = 1e9+7;
long long p[MAX_N], v[MAX_N], ans = 1;
int main(){
    int n, nrt, nh, cnt;    
    scanf("%d", &n);
    if(n <= 5) {printf("empty\n"); return 0;}
    nh = n / 2, nrt = sqrt(n), cnt = 0;
    for(int i = 1; i < MAX_N; i++) v[i] = i;
    for(int i = 2; i <= nh; i++){
        if(v[i] == i) p[++cnt] = i;
        for(int j = 1; j <= cnt; j++){
            if(p[j] > v[i] || i*p[j] > nh) break; 
            v[i*p[j]] = p[j];
        }
    }
    // 处理2
    p[0] = p[1];
    while(p[0] <= n / 3) p[0] *= p[1];
    ans = (p[0]/p[1]*ans)%mod;
    // 处理3、5、……
    for(int i = 2; i <= cnt; i++){
        p[0] = p[i];
        while(p[0] <= nh) p[0] *= p[i];
        ans = (p[0]/p[i]*ans)%mod;
    }
    printf("%d\n", ans);
    return 0;
}