原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=6833
目录
题意
∑ a 1 = 1 n ∑ a 2 = 1 n . . . ∑ a x = 1 n ( ∏ j = 1 n a j k ) f ( g c d ( a 1 , a 2 . . . a x ) ) g c d ( a 1 , a 2 . . a x ) \sum_{a_1=1}^{n}\sum_{a_2=1}^{n}...\sum_{a_x=1}^{n}(\prod_{j=1}^{n}a_j^k)f(gcd(a_1,a_2...a_x))gcd(a_1,a_2..a_x) a1=1∑na2=1∑n...ax=1∑n(j=1∏najk)f(gcd(a1,a2...ax))gcd(a1,a2..ax)
化简
令gcd(a1, a2…ax) = d
∑ a 1 = 1 n ∑ a 2 = 1 n . . . ∑ a x = 1 n ( ∏ j = 1 n a j k ) f ( d ) d \sum_{a_1=1}^{n}\sum_{a_2=1}^{n}...\sum_{a_x=1}^{n}(\prod_{j=1}^{n}a_j^k)f(d)d a1=1∑na2=1∑n...ax=1∑n(j=1∏najk)f(d)d
枚举d
∑
d
=
1
n
f
(
d
)
∑
a
1
=
1
n
∑
a
2
=
1
n
.
.
.
∑
a
x
=
1
n
(
∏
j
=
1
n
a
j
k
)
[
g
c
d
(
a
1
,
a
2
.
.
.
a
x
)
=
d
]
\sum_{d=1}^{n}f(d)\sum_{a_1=1}^{n}\sum_{a_2=1}^{n}...\sum_{a_x=1}^{n}(\prod_{j=1}^{n}a_j^k)[gcd(a_1,a_2...a_x) = d]
d=1∑nf(d)a1=1∑na2=1∑n...ax=1∑n(j=1∏najk)[gcd(a1,a2...ax)=d]
将gcd化为1
∑
d
=
1
n
f
(
d
)
d
k
x
+
1
∑
a
1
=
1
n
/
d
∑
a
2
=
1
n
/
d
.
.
.
∑
a
x
=
1
n
/
d
(
∏
j
=
1
n
a
j
k
)
[
g
c
d
(
a
1
,
a
2
.
.
.
a
x
)
=
1
]
\sum_{d=1}^{n}f(d)d^{kx+1}\sum_{a_1=1}^{n/d}\sum_{a_2=1}^{n/d}...\sum_{a_x=1}^{n/d}(\prod_{j=1}^{n}a_j^k)[gcd(a_1,a_2...a_x) = 1]
d=1∑nf(d)dkx+1a1=1∑n/da2=1∑n/d...ax=1∑n/d(j=1∏najk)[gcd(a1,a2...ax)=1]
对gcd反演
∑
d
=
1
n
f
(
d
)
d
k
x
+
1
∑
a
1
=
1
n
/
d
∑
a
2
=
1
n
/
d
.
.
.
∑
a
x
=
1
n
/
d
(
∏
j
=
1
n
a
j
k
)
∑
a
1
∣
t
,
a
2
∣
t
.
.
μ
(
t
)
\sum_{d=1}^{n}f(d)d^{kx+1}\sum_{a_1=1}^{n/d}\sum_{a_2=1}^{n/d}...\sum_{a_x=1}^{n/d}(\prod_{j=1}^{n}a_j^k)\sum_{a_1|t,a_2|t..}\mu(t)
d=1∑nf(d)dkx+1a1=1∑n/da2=1∑n/d...ax=1∑n/d(j=1∏najk)a1∣t,a2∣t..∑μ(t)
枚举t
∑
d
=
1
n
f
(
d
)
d
k
x
+
1
∑
t
=
1
n
/
d
μ
(
t
)
t
k
x
∑
a
1
=
1
n
/
t
d
∑
a
2
=
1
n
/
t
d
.
.
.
∑
a
x
=
1
n
/
t
d
(
∏
j
=
1
n
a
j
k
)
\sum_{d=1}^{n}f(d)d^{kx+1}\sum_{t=1}^{n/d}\mu(t)t^{kx}\sum_{a_1=1}^{n/td}\sum_{a_2=1}^{n/td}...\sum_{a_x=1}^{n/td}(\prod_{j=1}^{n}a_j^k)
d=1∑nf(d)dkx+1t=1∑n/dμ(t)tkxa1=1∑n/tda2=1∑n/td...ax=1∑n/td(j=1∏najk)
=
∑
d
=
1
n
f
(
d
)
d
k
x
+
1
∑
t
=
1
n
/
d
μ
(
t
)
t
k
x
(
∑
j
=
1
n
/
t
d
j
k
)
x
= \sum_{d=1}^{n}f(d)d^{kx+1}\sum_{t=1}^{n/d}\mu(t)t^{kx}(\sum_{j=1}^{n/td}j^k)^x
=d=1∑nf(d)dkx+1t=1∑n/dμ(t)tkx(j=1∑n/tdjk)x
令T = td，并枚举T
∑
T
=
1
n
T
k
x
(
∑
j
=
1
n
/
T
j
k
)
x
∑
d
∣
T
f
(
d
)
d
μ
(
T
/
d
)
\sum_{T=1}^{n}T^{kx}(\sum_{j=1}^{n/T}j^k)^x\sum_{d|T}f(d)d\mu(T/d)
T=1∑nTkx(j=1∑n/Tjk)xd∣T∑f(d)dμ(T/d)
我们令
h
(
T
)
=
∑
d
∣
T
f
(
d
)
d
μ
(
T
/
d
)
h(T) = \sum_{d|T}f(d)d\mu(T/d)
h(T)=d∣T∑f(d)dμ(T/d)
得到
∑
T
=
1
n
T
k
x
h
(
T
)
(
∑
j
=
1
n
/
T
j
k
)
x
\sum_{T=1}^{n}T^{kx}h(T)(\sum_{j=1}^{n/T}j^k)^x
T=1∑nTkxh(T)(j=1∑n/Tjk)x
然后我们预处理出
∑
T
=
1
n
T
k
x
h
(
T
)
的
前
缀
和
和
∑
j
=
1
n
/
T
j
k
的
值
\sum_{T=1}^{n}T^{kx}h(T)的前缀和和\sum_{j=1}^{n/T}j^k的值
T=1∑nTkxh(T)的前缀和和j=1∑n/Tjk的值
最终可以用一个整除分块解决
Code
#include <bits/stdc++.h>
using namespace std;
//#define ACM_LOCAL
#define re register
#define fi first
#define se second
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const double eps = 1e-4;
const int MOD = 1e9 + 7;
typedef long long ll;
typedef pair<int, int> PII;
ll prime[N], mu[N], k;
ll phi[N], f[N], h[N], sum1[N], sum2[N];
bool is_prime[N];
ll t, K, x;
ll ksm(ll a, ll b) {
ll res = 1, base = a;
while (b) {
if (b & 1) res = res * base % MOD;
base = base * base % MOD;
b >>= 1;
}
return res % MOD;
}
inline void init(int n) {
memset(is_prime, true, sizeof is_prime);
mu[1] = 1; phi[1] = 1; f[1] = 1;
for (re int i = 2; i < n; ++i) {
f[i] = 1;
if (is_prime[i]) prime[++k] = i, mu[i] = -1, phi[i] = i - 1;
for (re int j = 1; j <= k && i * prime[j] < n; ++j) {
is_prime[i * prime[j]] = false;
if (i % prime[j] == 0) {
phi[i * prime[j]] = phi[i] * prime[j];
break;
} else {
mu[i * prime[j]] = -mu[i];
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
}
for (ll kk = 2; kk * kk < n; kk++) {
for (ll j = kk * kk; j < n; j += kk * kk) {
f[j] = 0;
}
}
for (ll d = 1; d < n; d++) {
for (ll T = d; T < n; T += d) {
h[T] = (h[T] + f[d] * d % MOD * mu[T/d] % MOD + MOD) % MOD;
}
}
for (ll T = 1; T < n; T++) {
ll tmp1 = ksm(T, K);
sum1[T] = (sum1[T-1] + tmp1) % MOD;
sum2[T] = (sum2[T-1] + ksm(tmp1, x) * h[T] % MOD) % MOD;
}
}
ll calc(ll n) {
ll ans = 0;
for (ll l = 1, r; l <= n; l = r + 1) {
r = min(n, n / (n / l));
ans = (ans + (sum2[r] - sum2[l-1] + MOD) % MOD * ksm(sum1[n / l], x) % MOD) % MOD;
}
return ans;
}
void solve() {
cin >> t >> K >> x;
init(N);
while (t--) {
ll n; cin >> n;
printf("%lld\n", calc(n));
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef ACM_LOCAL
freopen("input", "r", stdin);
freopen("output", "w", stdout);
#endif
solve();
}