题意：给你一个T，x，k，表示有T次询问，每次询问给你一个n，求：
$$sum_{a_1=1}^{n}sum_{a_2=1}^{n}ldots sum_{a_x=1}^{n}left (prod_{j=1}^{x}a_j^k ight )f(gcd(a_1,a_2,ldots ,a_x)) * gcd(a_1,a_2,ldots ,a_x)$$
其中，如果x有平方因子，则f(x)=0，否则f(x)=1，$Tleq 10^4,1leq kleq 10^9,1leq xleq 10^9,1leq nleq 2 imes 10^5$
思路：先考虑一下f(x)的求法，将x质因子分解后，如果某一个质数的幂次$geq 2$，那么x一定有平方因子，那么f(x)=0，并且由莫比乌斯函数的定义有$mu(x)=0$，当f(x)=1时，$mu(x)=1$或者$mu(x)=-1$，所以可以得到$f(x)={mu(x)}^2$
$$sum_{a_1=1}^{n}sum_{a_2=1}^{n}ldots sum_{a_x=1}^{n}left (prod_{j=1}^{x}a_j^k ight )f(gcd(a_1,a_2,ldots ,a_x)) * gcd(a_1,a_2,ldots ,a_x)$$
令$gcd(a_1,a_2,ldots ,a_x)=d$
$$sum_{a_1=1}^{n}sum_{a_2=1}^{n}ldots sum_{a_x=1}^{n}left (prod_{j=1}^{x}a_j^k ight )f(d) * d [gcd(a_1,a_2,ldots ,a_x)==d]$$
把d提到最前面
$$sum_{d=1}^{n} sum_{a_1=1}^{frac{n}{d}}sum_{a_2=1}^{frac{n}{d}}ldots sum_{a_x=1}^{frac{n}{d}}(a_1 cdots a_x)^k * f(d) * d * d^{kx} [gcd(a_1,a_2,ldots ,a_x)==1]$$
运用反演公式
$$sum_{d=1}^{n} sum_{a_1=1}^{frac{n}{d}}sum_{a_2=1}^{frac{n}{d}}ldots sum_{a_x=1}^{frac{n}{d}}(a_1 cdots a_x)^k * f(d) * d * d^{kx} * sum_{j mid gcd} mu(j)$$
同样的，把j提到前面
$$sum_{d=1}^{n} sum_{j=1}^{frac{n}{d}} sum_{a_1=1}^{frac{n}{dj}}sum_{a_2=1}^{frac{n}{dj}}ldots sum_{a_x=1}^{frac{n}{dj}}(a_1 cdots a_x)^k * f(d) * d * d^{kx} * j^{kx} * mu(j)$$
由于$sum_{a_1=1}^{frac{n}{dj}}sum_{a_2=1}^{frac{n}{dj}}ldots sum_{a_x=1}^{frac{n}{dj}}(a_1 cdots a_x)^k={[1^k+2^k+cdots + (frac{n}{dj})^k]}^x$
$$sum_{d=1}^{n} sum_{j=1}^{frac{n}{d}} mu(j) * (dj)^{kx} * f(d) * d * {[1^k+2^k+cdots + (frac{n}{dj})^k]}^x$$
令T=dj
$$sum_{T=1}^n sum_{j mid T} mu(j) * T^{kx} * f(frac{T}{j}) * frac{T}{j} * {[1^k+2^k+cdots + (frac{n}{dj})^k]}^x$$
令$g(T)=sum_{j mid T} mu(j) * T^{kx} * f(frac{T}{j}) * frac{T}{j}$
枚举j的倍数预处理g(T)，直接预处理${[1^k+2^k+cdots + (frac{n}{dj})^k]}^x$
每次询问的时候对n数论分块，时间复杂度$Tsqrt n+nlogn$
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std; typedef long long ll; const int N = 200010; const ll mod = 1000000007; int T, n; int tot, isp[N], p[N], mu[N], f[N]; ll k, x, s[N], qmi[N], g[N]; void init(int n) { mu[1] = 1; for (int i = 2; i <= n; i++) { if (!isp[i]) { p[++tot] = i; mu[i] = -1; } for (int j = 1; j <= tot && p[j] <= n / i; j++) { isp[i * p[j]] = 1; if (0 == i % p[j]) { mu[i * p[j]] = 0; break; } else mu[i * p[j]] = -mu[i]; } } for (int i = 1; i <= n; i++) f[i] = mu[i] * mu[i]; } ll power(ll a, ll n) { ll res = 1; while (n) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); init(N - 5); scanf("%d%lld%lld", &T, &k, &x); for (int i = 0; i < N; i++) { qmi[i] = power(i, x * k % (mod - 1)); s[i] = power(i, k); } for (int i = 1; i < N; i++) s[i] = (s[i] + s[i - 1]) % mod; for (int i = 0; i < N; i++) s[i] = power(s[i], x); for (int i = 1; i <= N - 5; i++) { for (int j = 1; j <= (N - 5) / i; j++) { int t = i * j; ll tv = qmi[t] * mu[j] % mod * f[i] % mod * i % mod; g[t] = ((g[t] + tv) % mod + mod) % mod; } } for (int i = 1; i <= N - 5; i++) g[i] = (g[i] + g[i - 1]) % mod; while (T--) { scanf("%d", &n); ll res = 0; for (int l = 1, r = 0; l <= n; l = r + 1) { r = n / (n / l); ll t = ((g[r] - g[l - 1]) % mod + mod) % mod; t = t * s[n / l] % mod; res = (res + t) % mod; } printf("%lld ", res); } return 0; }