题目大意

即求

$$ S (n) = \sum^n_{\{ a_x \} = 1} \left( \prod_{j = 1}^x a_j \right)^k f (\gcd \{ a_x \}) \gcd \{ a_x \} $$

我自己随便简写了，全打太麻烦了。

分析

这东西看着很吓人，其实是纸老虎。首先 $f(x) = \mu(x)^2$。提出 $\gcd$ 有

$$ \begin{aligned} S (n) & =\sum_{d=1}^{n}\sum^{n}_{\{ a_{x}\}=1}(\prod_{j=1}^{x}a_{j})^{k}{\mu}(d)^{2}d [gcd \{ a_{x}\} =d]\\ & =\sum_{d=1}^{n}{\mu}(d)^{2}d^{k x+1}\sum^{n/d}_{\{ a_{x}\} =1}(\prod_{j=1}^{x}a_{j})^{k}[gcd \{ a_{x}\} =1] \end{aligned} $$

对后面这部分反演有

$$ \begin{aligned} & \sum^{n / d}_{\{ a_x \} = 1} \left( \prod_{j = 1}^x a_j \right)^k \left( \sum_{t \mid \gcd \{ a_x \}} \mu (t) \right)\\ = & \sum^{n / d}_{\{ a_x \} = 1} \left( \prod_{j = 1}^x a_j \right)^k \left( \sum_{t = 1}^{n / d} [t \mid \gcd \{ a_x \}] \mu (t) \right)\\ = & \sum_{t = 1}^{n / d} \mu (t) t^{k x} \sum^{n / d t}_{\{ a_x \} = 1} \left( \prod_{j = 1}^x a_j \right)^k \end{aligned} $$

代回去，枚举 $T = d t$

$$ \begin{aligned} S (n) & = \sum_{d = 1}^n d \mu (d)^2 (d t)^{k x} \sum_{t = 1}^{n / d} \mu (t) \sum^{n / d t}_{\{ a_x \} = 1} \left( \prod_{j = 1}^x a_j \right)^k\\ & = \sum_{T = 1}^n \sum_{d \mid T} d \mu (d)^2 T^{k x} \mu \left(\frac{T}{d} \right) \sum^{n / T}_{\{ a_x \} = 1} \left( \prod_{j = 1}^x a_j \right)^k\\ & = \sum_{T = 1}^n T^{k x} \left( \sum^{n / T}_{\{ a_x \} = 1} \left( \prod_{j = 1}^x a_j \right)^k \right) \sum_{d \mid T} d \mu (d)^2 \mu \left( \frac{T}{d} \right)\\ & = \sum_{T = 1}^n T^{k x} \left( \sum^{n / T}_{i = 1} i^k \right)^x \sum_{d \mid T} d \mu (d)^2 \mu \left( \frac{T}{d} \right) \end{aligned} $$

到这里已经差不多化完了。令

$$ G (x) = \sum^x_{i = 1} i^k, H (x) = \sum_{d \mid x} d \mu (d)^2 \mu \left( \frac{x}{d} \right) $$

其中 $G (x)$ 显然可以预处理，而 $H (x)$ 是积性函数的卷积，故也是积性函数，其中

$$ H (p^c) = \begin{cases} p - 1,& c = 1\\ -p, & c = 2 \\ 0, & c > 2 \end{cases} $$

可以线性筛得到。

const ll maxn = 2e5 + 86;
const ll mod = 1e9 + 7;
#define ACM_MOD mod

bool notp[maxn + 10];
int prime[maxn/10 + 10], cnt;
ll hh[maxn + 10];
void sieve(int n) {
	hh[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!notp[i]) {
			prime[++cnt] = i;
			hh[i] = i - 1;
		}
		int t = n / i;
		for (int j = 1; j <= cnt;j++) {
			int pj = prime[j], ti = i * pj;
			if (pj > t)
				break;
			notp[ti] = true;
			if (i % pj == 0) {
				int tj = i / pj;
				if (tj % pj != 0) {
					hh[ti] = hh[tj] * (mod - pj) % mod;
				} else {
					hh[ti] = 0;
				}
				break;
			}
			hh[ti] = hh[i] * hh[pj] % mod;
		}
	}
}

总之

$$ S (n) = \sum_{T = 1}^n T^{k x} H (T) G \left( \left\lfloor \frac{n}{T} \right\rfloor \right)^x $$

可以用整数分块。

#include "template/basic/qpow.hpp"

ll gg[maxn + 10];

void pre(ll k, ll x) {
	sieve(maxn);
	for (ll i = 1; i <= maxn; i++) {
		gg[i] = (gg[i - 1] + qpow(i, k)) % mod;
	}
	for (ll i = 1; i <= maxn; i++) {
		hh[i] = (hh[i - 1] + qpow(i, k * x % (mod - 1)) * hh[i]) % mod;
		gg[i] = qpow(gg[i], x);
	}
}

int main() {
	ll ttt = rr(), k = rr(), x = rr();
	pre(k, x);
	while(ttt--) {
		ll n = rr();
		ll ans = 0;
		for (ll l = 1, r; l <= n; l = r + 1) {
			r = n / (n / l);
			ll tsum = hh[r] - hh[l - 1] + mod;
			tsum = tsum * gg[n / l] % mod;
			ans = ans + tsum;
		}
		printf("%lld\n", ans % mod);
	}
	return 0;
}