幂数 (Powerful Number) 是指一正整数 $n$，其所有质因数的平方亦是 $n$ 的因数，换言之，若存在一质因数 $p$，则 $p^2$ 也是 $n$ 的因数。很显然，幂数的个数是无限的。
给定一个正整数 $n$，你需要求出所有幂数中 $\leq n$ 的个数以及它们的和。
不超过 $100$ 的幂数有：$1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 72, 81, 100$。
共一行，包含一个正整数 $n$ ($1 \leq n \leq 10^{25}$)。
输出两行，每行一个整数。第一行的数表示所有幂数中 $\leq n$ 的个数，第二行的数表示它们的和。
先抛结论：$n$ 为幂数 (Powerful) 的充要条件是，存在正整数 $a, b$，满足 $n = a^2 b^3$。若规定 $b$ 平方松 (square-free)，则这样的表示是唯一的。
证明：充分性显然。必要性：考虑 $p \mid n$，记 $\alpha = v_p (n)$，则 $\alpha \geq 2$，则令 $\gamma = \alpha \bmod 2, \beta = \dfrac 12 \left( \alpha - 3 \gamma \right)$，则易知 $\beta \geq 0, \gamma \in \left\{ 0, 1 \right\}$。
于是我们令 $a$ 中 $p$ 的指数为 $\beta$，$b$ 中 $p$ 的指数为 $\gamma \in \left\{ 0, 1 \right\}$。容易验证此时 $n = a^2 b^3$，且 $b$ 平方松。且只有这么构造才能使 $b$ 平方松。
于是，我们如果枚举平方松的 $b$，然后对于每个 $1 \leq a \leq \sqrt {\dfrac n {b^3}}$，都有唯一的一个幂数与之对应。
因此幂数的总数就应该等于 $$ \sum_{i=1}^n \mu^2 (i) \cdot \sqrt{ \left \lfloor \frac n {i^3} \right \rfloor} \tag 1 \label 1 $$
所有幂数的和等于 $$ \sum_{i=1}^n \mu^2 (i) \cdot i^3 \cdot S_2 \left(\sqrt{ \left \lfloor \frac n {i^3} \right \rfloor} \right) \tag 2 \label 2 $$
其中 $S_2(n) = 1^2 + 2^2 + \cdots + n^2 = \dfrac 16 n (n + 1) (2n + 1)$。
看起来是 $\eqref 1$ 式较 $\eqref 2$ 式简单，我们先来解决 $\eqref 1$。
还是整数分块。
考察 $\sqrt{ \left \lfloor \dfrac n {i^3} \right \rfloor}$ 的取值，当 $i \leq n^{1/5}$ 时，有 $O \left( n^{1/5} \right)$ 种取值，当 $i > n^{1/5}$ 时，由于 $\sqrt{ \left \lfloor \dfrac n {i^3} \right \rfloor} \leq n^{1/5} + \epsilon$，因此取值也不超过 $O \left( n^{1/5} \right)$。因此 $\sqrt{ \left \lfloor \dfrac n {i^3} \right \rfloor}$ 一共只有 $O \left( n^{1/5} \right)$ 中取值。
而 $n^{1/5} \leq 10^5$ 是可接受的，因此我们暴力整除分块即可解决该问题。
接下来还是那个历史遗留问题：求 $\displaystyle \sum_{i=1}^n \mu^2 (i)$，这是个经典问题，可以在 $O \left( n^{1/3} \right)$ 时间内解决。具体参见 [loj509]动态几何问题。
总的时间复杂度可以使用积分近似计算为 $O \left( n^{4/15} \right)$。
接下来考虑稍难一点的 $\eqref 2$ 式，依旧还是整除分块，只是现在我们要求的是 $\displaystyle \sum_{i=1}^n \mu^2 (i) \cdot i^3$。
更一般地，我们考虑求 $\displaystyle \sum_{i=1}^n \mu^2 (i) \cdot i^k$ ($k \in \mathbb N$)。
按照那道题最后的反演公式：$\displaystyle \mu^2 (n) = \sum_{d^2 \mid n} \mu(d)$，我们有
$$ \sum_{i=1}^n \mu^2 (i) \cdot i^k = \sum_{i=1}^n \left( \sum_{d^2 \mid i} \mu(d) \right) i^k = \sum_{i=1}^n \sum_{d^2 \mid i} \mu(d) \cdot d^{2k} \cdot \left( \frac i {d^2} \right)^k = \sum_{d=1}^{\left \lfloor \sqrt n \right \rfloor} \mu(d) \cdot d^{2k} \cdot \sum_{d^2 \mid i} \left( \frac i {d^2} \right)^k = \sum_{d=1}^{\left \lfloor \sqrt n \right \rfloor} \mu(d) \cdot d^{2k} \cdot S_k \left( \left \lfloor \frac n {d^2} \right \rfloor \right) $$
其中 $S_k (n) = 1^k + 2^k + \cdots + n^k$ 为关于 $n$ 的一个 $k + 1$ 次多项式 (貌似用容斥也可以推的样子)。
因此，只要维护出 $\mu(i) \cdot i^{2k}$ 的前缀和，就同样可以在 $O \left( n^{1/3} \right)$ 时间内完成计算。
记得计算时要开 __int128 (或 Python)，总时间复杂度还是 $O \left( n^{4/15} \right)$。
#include <bits/stdc++.h>
#define ID isdigit(c = getchar())
typedef long long ll;
typedef __int128 lll;
const ll N = 2003731, D = 23333;
void getint(lll &x) {
int c;
for (; !ID; ) if (!~c) return;
for (x = c & 15; ID; x = x * 10 + (c & 15));
}
void putint(lll x) {
static char buf[54];
if (!x) {putchar(48); return;} int i = 0;
for (; x; x /= 10) buf[++i] = x % 10 | 48;
for (; i; --i) putchar(buf[i]);
}
lll n;
int pn, p[1272460];
int smu2[N];
short mu[N];
lll smu2i3[N], mui6[D];
inline lll S2(ll n) {return (lll)n * (n + 1) * (n << 1 | 1) / 6;}
inline lll S3(ll n) {lll r = (lll)n * (n + 1) / 2; return r * r;}
inline lll P6(int n) {lll r = (ll)n * n; return r * r * r;}
void sieve(int n) {
int i, j, v;
memset(mu, 1, sizeof mu); mu[0] = 0; mu[1] = 1;
for (i = 2; i <= n; ++i) {
if (mu[i] > 1) p[pn++] = i, mu[i] = -1;
for (j = 0; j < pn && (v = i * p[j]) <= n; ++j)
if (i % p[j]) mu[v] = -mu[i];
else {mu[v] = 0; break;}
}
for (i = 1; i <= n && i < D; ++i) mui6[i] = mui6[i - 1] + mu[i] * P6(i);
for (i = 1; i <= n && i < N; ++i) smu2i3[i] = smu2i3[i - 1] + (mu[i] ? (lll)i * i * i : 0);
for (i = 1; i <= n; ++i) smu2[i] = smu2[i - 1] + !!mu[i], mu[i] += mu[i - 1];
}
ll square_root(lll n) {
ll ret = sqrtl(n);
for (; (lll)ret * ret < n; ++ret);
for (; (lll)ret * ret > n; --ret);
return ret;
}
ll cube_root(lll n) {
ll ret = cbrtl(n);
for (; (lll)ret * ret * ret < n; ++ret);
for (; (lll)ret * ret * ret > n; --ret);
return ret;
}
ll sum_mu2(ll n) {
if (n < N) return smu2[n];
ll i, j, ni2, ret = 0;
for (i = sqrtl(n + .2); i; i = j) {
ni2 = n / (i * i);
j = (i < ni2 ? i - 1 : sqrtl(n / (ni2 + 1) + .2));
ret += ni2 * (mu[i] - mu[j]);
}
return ret;
}
lll sum_mu2i3(ll n) {
if (n < N) return smu2i3[n];
ll i, j, ni2; lll ret = 0;
for (i = sqrtl(n + .2); i; i = j) {
ni2 = n / (i * i);
j = (i < ni2 ? i - 1 : sqrtl(n / (ni2 + 1) + .2));
ret += S3(ni2) * (mui6[i] - mui6[j]);
}
return ret;
}
int main() {
ll i, j, count = 0, si, sj, ni3;
lll Si, Sj, Sni3, sum = 0;
getint(n);
sieve(n >= N ? N - 1 : n);
i = cube_root(n), si = sum_mu2(i), Si = sum_mu2i3(i);
for (; i; si = sj, Si = Sj, i = j) {
ni3 = square_root(n / ((lll)i * i * i));
Sni3 = S2(ni3);
j = (i < ni3 ? i - 1 : cube_root(n / ((lll)(ni3 + 1) * (ni3 + 1))));
sj = sum_mu2(j);
Sj = sum_mu2i3(j);
count += ni3 * (si - sj);
sum += Sni3 * (Si - Sj);
}
printf("%lld\n", count);
putint(sum); putchar(10);
return 0;
}
坑1：在求 $\displaystyle \sum_{i=1}^n \mu^2 (i)$ 和 $\displaystyle \sum_{i=1}^n \mu^2 (i) \cdot i^3$ 时可以适当使用线性筛优化，不过不要筛太多，不能让它成为瓶颈。
坑2：在整除分块中注意常数，避免重复计算和不必要的开根等。