https://projecteuler.net/problem=516

。。观察符合条件的原数 x 的 Pattern。。
显然形如
x = p1p2p3…pn2^a3^b5^c
且 pi = 2^d3^e^5^f + 1
。。。

const int PMAX = 1000000;
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


inline bool isPrime(LL n){
    ECH(it, P){
        if (*it >= n) return true;
        if (n % *it == 0) return false;
    }
    return true;
}


vector<LL> PP, P235; LL n;


void dfs1(int k = 0, LL n = 1){
    if (k == 3){
        P235.PB(n);
        if (n+1 > 5 && n+1 <= ::n && isPrime(n+1)) PP.PB(n+1);
    }
    else{
        do{
            dfs1(k+1, n);
            n *= P[k];
        } while (n <= ::n);
    }
}
uint z = 0;


void dfs3(int k, LL n){
    ECH(it, P235){
        if ((double)*it * n <= ::n){
            z += *it * n;
        }
    }
}

void dfs2(int k = 0, LL n = 1){
    if (k == PP.size()){
        dfs3(0, n);
    }
    else{
        dfs2(k+1, n);
        if (n  <= ::n / PP[k] ) dfs2(k+1, n * PP[k]);
    }
}


int main(){
    
#ifndef ONLINE_JUDGE
    freopen("/users/xiaodao/desktop/Exercise/in.txt", "r", stdin);
    //freopen("/users/xiaodao/desktop/Exercise/out.txt", "w", stdout);
#endif

    sieve(); n = 1e12;
    dfs1(); SRT(PP); SRT(P235);    
    dfs2();
    cout << z << endl;
    
}

Posted by xiaodao
Category: PE
Tags: 暴搜