【2021寒假集训营第一场】J-一群小青蛙呱蹦呱蹦呱

#include<bits/stdc++.h>

using namespace std;
int n;
const long long mod = 1e9+7;
bool b[80000100];
int  p[10000000];
int cnt = 0;
long long ksm(int a, int b)
{
    long long ans= 1, t= a;
    while(b)
    {
        if (b & 1) ans = ans * t % mod;
        t = t * t %mod;
        b >>= 1;
    }
    return ans;
}
long long calc(int x)
{
    //cout << log(n/3)/ log(2)<<endl;
    if (x == 2)
        return ksm(2, floor(log(n/3)/ log(2)));
    return ksm(x, floor(log(n/2)/ log(x)));
}
int main(){
    cin>> n;
    long long ans = 1;
    memset(b, 1, sizeof(b));

    for(int i = 2;i <= n/2; i++)
    {
        if(b[i])
        {
            p[cnt++] = i;
            ans = (ans * calc(i)) % mod;
        }
        for(int j = 0;j < cnt && i*p[j] <= n/2; j++)
        {
            b[i*p[j]] = 0;
            if(i % p[j] == 0) break;
        }
    }
    if (ans == 1) cout <<"empty";
    else cout <<ans;

    return 0;
}