（一）一群小青蛙呱蹦呱蹦呱

题目描述：

链接：https://ac.nowcoder.com/acm/contest/9981/J
来源：牛客网

有n个格子，每个格子里有一个数，1,2,3,4…n

牛牛放出无穷只青蛙。

第一只青蛙的路线是：1->2->4->8->16->….

第二只青蛙的路线是：1->3->9->27->81->….

第三只青蛙的路线是：1->5->25->125….

第四只青蛙的路线是：1->7->49……..

。。。。。。

用数学语言描述，第 i只青蛙的路线是首项为1，公比为p(i)的等比数列，其中p(i)代表第个素数。

当青蛙跳到一个格子上，如果这个格子上面有一个数，青蛙就会把这个数吃掉。

牛牛想知道，所有没有被吃掉的数的lcm（最小公倍数 ，Least common multiple）是多少？

由于这个lcm可能非常大，请输出它对10⁹ + 7取模的值。

输入描述：

一个整数n

1 <= n <= 1.6 * 10⁸

输出描述：

如果所有数都被吃掉了，请输出一个字符串”empty”

否则输出所有没有被吃掉的数的lcm，对模10⁹ + 7

思路：

#include<bits/stdc++.h>
#include<iostream>
#include<queue>
#include<sstream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#define inf 0x3f3f3f3f
#include<cstring>
#include<cstdio>
#define  ll long long
#define PI acos(-1)
#define mset(s, _) memset(s, _, sizeof(s))
//#define lo
using namespace std;
void coutx(double q, int x)
{
    //cout.setf(ios::fixed);
    //cout.unsetf(ios::fixed);
    cout << fixed << setprecision(x) << q << endl;
    return ;
}
inline ll ksc(ll x, ll y, ll mod)//快速乘
{
    return ( x * y - (ll) ( (long double) x / mod*y )*mod + mod ) % mod;
}
ll gcd(ll a,ll b)
{
    return b==0?a:gcd(b,a%b);
}
ll lcm(ll a,ll b)
{
    return a/gcd(a,b)*b;
}
const int mod1 = 1e9 + 7;
const int N = 8e7+7;
bool isprime[N];
ll vis[N];
int sieve(int n)//线性筛
{
    int cnt = 0;
    isprime[0] = isprime[1] = true;
    for(int i = 2; i <= n; i ++)
    {
        if(!isprime[i])        vis[ ++ cnt] = i;
        for(int j = 1; j <= cnt && i * vis[j] <= n; j ++)
        {
            isprime[i * vis[j]] = 1;
            if(i % vis[j] == 0)
                break;
        }    
    }
    return cnt;
}
int log(int n, int m)
{
    ll res = 0;
    ll t = 1;
    while(t <= m)
    {
        t *= n;
        res ++;
    }
    return res - 1;
}
ll poww(ll a, ll b)//快速幂
{
    ll ans = 1;
    while(b)
    {
        if(b & 1) 
            ans = ksc(ans, a, mod1) % mod1;
        a = ksc(a, a, mod1) % mod1;
        a %= mod1;
        b >>= 1;
        ans %= mod1;
    }
    return ans % mod1;
 } 
int main()
{
    #ifdef lo
     freopen("data.in","r",stdin);
     freopen("data.out","w",stdout);
    #endif
    srand((unsigned int)time(0));
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, cnt;
    ll ans;
    cin >> n;
    if(n <= 5)
    {
        cout << "empty";
        return 0;
    }
    cnt = sieve(n / 2);
    ans = poww(2, log(2, n / 3));
    for(int i = 2; i <= cnt; i ++)
    {
        ans = (ans % mod1) * poww(vis[i], log(vis[i], n / 2));
        ans %= mod1;
    }
    cout << ans % mod1;
    return 0;
 }