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;
}
