https://projecteuler.net/problem=501

如何一次筛法求出所有的解？拆成两个数组，大小都小于 sqrt(n)：

- F[i]: 小于等于 i 的 PrimePi。
- G[i]: 小于等于 n/i 的 PrimePi。

//}/* .................................................................................................................................. */ const int PMAX = 1000000 + 1; vector<LL> P; bitset<PMAX> isC; LL n, nn; int PP[PMAX]; bool isPrime(LL x){ ECH(it, P){ if (sqr(*it) > x) break; if (x % *it == 0) return false; } return true; } #define ii (i*P[j]) #include <unordered_map> unordered_map<LL, LL> F, G; void sieve(){ nn = sqrt(n); FOR(i, 2, nn+1){ if (!isC[i]) P.PB(i); for (int j=0;j<SZ(P)&&ii<nn;++j){ isC[ii]=1; if (!(i%P[j])) break; } } REP_1(i, nn+1){ F[i] = i-1; G[i] = n/i - 1; } FOR_1(p, 2, nn+1) if (F[p-1] != F[p]){ LL pp = (LL) p * p; LL up = min(nn, n / pp); REP_1(q, up){ LL d = (LL)p * q; if (d <= nn) G[q] -= G[d] - F[p-1]; else G[q] -= F[n/d] - F[p-1]; } DWN_1(i, nn+1, pp-1) F[i] -= F[i/p] - F[p-1]; } } LL f(LL n){ LL r = sqrt(n); vector<LL> V; REP_1(i, r+1) V.PB(n/i); int up = int(*V.rbegin()); DWN_1(i, up-1, 1) V.PB(i); Int z = 0; unordered_map<LL, LL> dp; REP(i, V.size()){ LL x = V[i]; dp[x] = x-1; } FOR_1(p, 2, r+1) if (dp[p] > dp[p-1]){ LL pp = (LL)p*p; for(auto v: V){ if (v < pp) break; dp[v] -= (dp[v/p] - dp[p-1]); } } return dp[n]; } LL z = 0; int main(){ #ifndef ONLINE_JUDGE freopen("/users/xiaodao/desktop/Exercise/in.txt", "r", stdin); // freopen("out.txt", "w", stdout); #endif n = 1e12; sieve(); z = 0; ECH(it, P){ if (pow(*it, 7) > n) break; z += 1; } REP(i, P.size()){ LL t = n / cub(P[i]); if (!t) break; z += t <= nn ? F[t] : G[cub(P[i])]; if (t >= P[i]) z -= 1; FOR(j, i+1, P.size()){ LL x = P[i] * P[j]; if (n/x > P[j]){ z += n/x <= nn ? F[n/x] : G[x]; z -= j+1; } else break; } } cout << z << endl; } // 197912312715