https://projecteuler.net/problem=500

堆。

//}/* .................................................................................................................................. */


const int PMAX = int(1e7) + 9;
VI P; bitset<PMAX> isC;
#define ii (i*P[j])
void sieve(){
    FOR(i, 2, PMAX){
        if (!isC[i]) P.PB(i);
        for (int j=0;j<SZ(P)&&ii<PMAX;++j){
            isC[ii]=1; if (!(i%P[j])) break;
        }
    }
}
#undef ii


int main(){
    
#ifndef ONLINE_JUDGE
    freopen("/users/xiaodao/desktop/Exercise/in.txt", "r", stdin);
    //freopen("/users/xiaodao/desktop/Exercise/out.txt", "w", stdout);
#endif
    
    priority_queue<LL, vector<LL>, greater<LL> > Q;

    sieve(); ECH(it, P) Q.push(*it);
    
    Int z = 1; int n = 500500;
    
    DO(n){
        LL u = Q.top(); Q.pop(); z *= u;
        if (double(u) * u < INFF) Q.push(u*u);
    }
    
    OT(z);
}

//35407281

Posted by xiaodao
Category: PE