题意
$$求解\sum_{a_1=1}^m…\sum_{a_n=1}^m\prod_{i=1}^na_i^k[gcd(a_1,a_2…,a_n)=d]$$
思路
$$\sum_{a_1=1}^{\frac{m}{d}}…\sum_{a_n=1}^{\frac{m}{d}}\prod_{i=1}^na_i^kd^k[gcd(a_1,a_2…,a_n)=1]$$
$注意有一个d^k！$
$$d^k\sum_{a_1=1}^{\frac{m}{d}}…\sum_{a_n=1}^{\frac{m}{d}}\prod_{i=1}^na_i^k\sum_{ta_1…ta_n}\mu(t)$$
$变换枚举顺序：$
$$d^{nk}\sum_{t=1}^{\frac{m}{d}}\mu(t)\sum_{a_1=1}^{\frac{m}{td}}…\sum_{a_n=1}^{\frac{m}{td}}\prod_{i=1}^na_i^kt^k$$
$$d^{nk}\sum_{t=1}^{\frac{m}{d}}t^{nk}\mu(t)\sum_{a_1=1}^{\frac{m}{td}}…\sum_{a_n=1}^{\frac{m}{td}}\prod_{i=1}^na_i^k$$
$这里有一个玄学:$
$$\sum_{a_1=1}^{\frac{m}{td}}…\sum_{a_n=1}^{\frac{m}{td}}\prod_{i=1}^na_i^k=(\sum_{i=1}^{\frac{m}{td}}i^k)^n$$
$因为a可取的值再[1,\frac{m}{td}]，而后面那个你可以想成完全平方的概念，更高的数学意义就是每个数都去的所有贡献。$
$多体会体会，很黑科技。$
$最后答案为：$
$$d^{nk}\sum_{t=1}^{\frac{m}{d}}t^{nk}\mu(t)(\sum_{i=1}^{\frac{m}{td}}i^k)^n$$
$注意n要欧拉降幂处理。总复杂度为O(n*\logn*\logn+T*\frac{m}{d})$
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| ##include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
const ll mod = 59964251;
const ll phi = 59870352;
bool is\_prime[N];
int prime[N], cnt, mu[N];
void init() {
mu[1] = 1;
for(int i = 2;i < N; i++) {
if(!is\_prime[i]) prime[++cnt] = i, mu[i] = -1;
for(int j = 1;j <= cnt && i * prime[j] < N; j++) {
is\_prime[i * prime[j]] = 1;
if(i % prime[j] == 0) {
mu[i * prime[j]] = 0;
break;
}
else mu[i * prime[j]] = -mu[i];
}
}
}
ll quick\_pow(ll a, ll b) {
ll ans = 1;
while(b) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans % mod;
}
void solve() {
init();
int \_; cin >> \_;
while(\_--) {
string n; cin >> n;
ll p = 0;
for(int i = 0;i < n.length(); i++) {
p = p * 10 + n[i] - '0';
p = p % phi + phi;
}
ll m, k, d; cin >> m >> d >> k;
vector<ll> f(m / d + 10), F(m / d + 10);
for(int i = 1;i <= m / d; i++) {
f[i] = (f[i - 1] + quick\_pow(i, k)) % mod;
F[i] = quick\_pow(f[i], p);
}
ll ans = 0;
for(int i = 1;i <= m / d; i++) {
ans = (ans + quick\_pow(i, p * k) * mu[i] * F[m / (i * d)]) % mod;
}
ans = ans * quick\_pow(d, p * k) % mod;
cout << (ans % mod + mod) % mod << endl;
}
}
signed main() {
solve();
}
|
本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/04/11/2019-icpc-yinchuan-easy-problem/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！