题目大意

定义

$$ f (n) = \sum_{d \mid n} d \left[ \gcd \left( d, \frac{n}{d} \right) = 1 \right] $$

求其前缀和 $S(n)$。

分析

首先 Min25 筛是过不了的，内存不够。先推式子

$$ \begin{aligned} S (n) &= \sum_{i = 1}^n \sum_{d \mid i} d \left[ \gcd \left( d, \frac{i}{d} \right) = 1 \right] \\ &= \sum_{d = 1}^n \sum_{i = 1}^n d [d \mid i] \left[\gcd \left( d, \frac{i}{d} \right) = 1 \right] \\ &= \sum_{d = 1}^n \sum_{i = 1}^{n / d} d [\gcd (i, d) = 1] \end{aligned} $$

看到 $\gcd = 1$ 就应该想起来 Mobius 反演，容易化简有

$$ S (n) = \sum_{d = 1}^n \sum_{i = 1}^{n / d} d \sum_{u \mid \gcd (i, d)} \mu(u) = \sum_{u = 1}^{\sqrt{n}} u \mu (u) \sum_{d = 1}^{n / u^2} d \left\lfloor \frac{n}{d u^2} \right\rfloor $$

用数论分块即可，计算复杂度 $O ( \sqrt{n} \log n )$。

const ll maxn = 1e6 + 20;
const ll mod = 1e9 + 7;

bool notp[maxn];
int prime[maxn / 10], cnt;
ll mu[maxn];
void sieve(int n); // 筛 Mobius 函数

ll g[maxn];

ll G(ll n) {
	if (n <= 1e6 && g[n] > 0)
		return g[n]; // 不做记忆化会 T
	__int128_t ret = 0;
	for (ll l = 1, r; l <= n; l = r + 1) {
		r = n / (n / l);
		__int128_t t = __int128_t(l + r) * (r - l + 1) / 2;
		ret += t * (n / l);
	}
	if (n <= 1e6)
		g[n] = ret % mod;
	return ret % mod;
}

int main() {
	ll ttt = rr();
	sieve(1e6 + 1);
	for (ll i = 1; i <= 1e6+1; i++) {
		mu[i] = (mu[i - 1] + mu[i] * i) % mod;
	}
	while (ttt--) {
		ll n = rr(), sn = sqrt(n * 1.0);
		__int128_t ans = 0;
		for (ll l = 1, r; l <= sn; l = r + 1) {
			ll t = n / l / l;
			r = sqrt(n / (n / l / l) * 1.0);
			ans += (mu[r] - mu[l - 1]) * G(n / l / l);
		}
		ans = (ans % mod + mod) % mod;
		printf("%lld\n", ll(ans));
	}
	return 0;
}