传送门：https://ac.nowcoder.com/acm/contest/7329/F
题意
求解：$f_i\;\;mod\;\;998244353\;\;(1\leq i\leq n)$。
思路
前置技能：$\mu*I =\varepsilon \;\;\;\; \sigma _q=id_q*I\;\;\;\;F(n)=\sum_{dn}\mu(i)f(\frac{n}{d})$
$$\sum_{in}f(i)\sigma_p(\frac{n}{i})=\sigma _q(n)\;\;->\;\;(f*\sigma_p )n=\sigma_q(n)$$
先将$\sigma$ 分解：
$$(f*id_p*I)n=(id_q*I)n$$
左右都乘上$\mu:$
$$(f*id_p)n=id_q(n)$$
$$\sum_{in}f(i)\frac{n^p}{i^p}=n^q$$
$$\sum_{in}\frac{f(i)}{i^p}=n^{q-p}=id_{q-p}(n)$$
反演得：
$$\frac{f(n)}{n^p}=\sum_{in}\frac{\mu(i)*n^{q-p}}{i^{q-p}}$$
$$\frac{f(n)}{n^q}=\sum_{in}\frac{\mu(i)}{i^{q-p}}$$
因为积性函数卷积性函数之后还是积性函数，所以能得到$\frac{f(n)}{n^q}$是积性函数。我们考虑与n互质的d，计算$f(d^k)$并且由莫比乌斯函数的性质得：
$$\frac{f(d^k)}{d^{kq}}=1-\frac{[k\ne 0]}{d^{q-p}}$$ $(根据上式，只有i=1或d时才\mu(i)满足，其他都是0)$
$所以再来看n，由基本算数定理得：n=p_1^{k_1}p_2^{k_2}…p_m^{k_m}，即：$
$$\frac{f(n)}{n^q}=\frac{f(p_1^{k_1})}{p_1^{qk_1}}\frac{f(p_2^{k_2})}{p_2^{qk_2}}…\frac{f(p_m^{k_m})}{p_m^{qk_m}}$$
$$\frac{f(n)}{n^q}=\prod_{dn \&\&d\;is\;a\;prime}(1-\frac{1}{d^{q-p}})$$
提前用欧拉筛处理$f(p^k)$即可，注意g数组的含义，因为当$i%prime[j]=0$时，$prime[j]$已经是$prime[j]*i$的因子的，而$f[i]$和$f[i*prime[j]]$两者之间的区别就是$prime[j]^q$，这还是比较难想到的。
Code(477MS)
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
##include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;
##define INF 0x7f7f7f
##define mem(a, b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)
const ll mod = 998244353;
const int N = 1e7 + 10;
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;
}
int prime[N];
bool is_prime[N];
int cnt;
ll q, p, n;
ll f[N], g[N];
void Eluer() {
is_prime[1] = is_prime[0] = true;
f[1] = 1;
for(int i = 2;i < N; i++) {
if(!is_prime[i]) {
prime[cnt++] = i;
g[i] = quick_pow(i, q);
f[i] = (g[i] - quick_pow(i, p)) % mod;
}
for(int j = 0;j < cnt && prime[j] * i < N; j++) {
is_prime[i * prime[j]] = true;
if(i % prime[j] == 0) {
f[i * prime[j]] = f[i] * g[prime[j]] % mod;
break;
}
f[i * prime[j]] = f[i] * f[prime[j]] % mod;
}
}
}
void solve() {
cin >> n >> p >> q;
Eluer();
ll ans = 0;
for(int i = 1;i <= n; i++) {
f[i] = (f[i] % mod + mod) % mod;
ans ^= f[i];
}
cout << ans << endl;
}
signed main() {
ios_base::sync_with_stdio(false);
##ifdef FZT_ACM_LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
signed test_index_for_debug = 1;
char acm_local_for_debug = 0;
do {
if (acm_local_for_debug == '$') exit(0);
if (test_index_for_debug > 20)
throw runtime_error("Check the stdin!!!");
auto start_clock_for_debug = clock();
solve();
auto end_clock_for_debug = clock();
cout << "Test " << test_index_for_debug << " successful" << endl;
cerr << "Test " << test_index_for_debug++ << " Run Time: "
<< double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
cout << "--------------------------------------------------" << endl;
} while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug));
##else
solve();
##endif
return 0;
}
|
本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2020/10/03/nowcoder-practice69-f/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！