JZOJ 5250.质数

首先转换一下,考虑 \(2^{f(i)}\) 的组合意义。
相当于把 \(i\) 的不同质因子分别分到两个数里面。
于是 \(2^{f(i)} = \sum\limits_{d|i} [\gcd(d,\dfrac id) = 1]\)

于是就简单了。 \[\begin{align*} & \sum\limits_{i=1}^n\sum\limits_{d|i}[\gcd(d,\dfrac id)=1] \\ = & \sum\limits_{d=1}^n\sum\limits_{id\le n}[\gcd(d,i)=1] \\ = & \sum\limits_{d=1}^n\sum\limits_{id\le n}\sum\limits_{k|\gcd(d,i)}\mu(k) \\ = & \sum\limits_{k^2\le n}\mu(k)\sum\limits_{ik^2\le n}\left\lfloor\dfrac n{ik^2}\right\rfloor \\ = & \sum\limits_{k=1}^{\lfloor\sqrt n\rfloor}\mu(k)\sum\limits_{i=1}^{\left\lfloor\frac n{k^2}\right\rfloor}\left\lfloor\dfrac n{ik^2}\right\rfloor \end{align*}\]

枚举 \(k\) 然后数论分块算后面的式子就好了,大概是 \(O(\sqrt n \log n)\) 的样子?
注意取模呀……\(n\) 是会爆模数的……

代码:

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
#include <cstdio>
#include <cmath>
using namespace std;
const int MX = 1e6;
const long long mod = 998244353;
long long n;
int vis[MX + 5],prime[MX + 5],cnt;
long long mu[MX + 5];
long long ans;
int main()
{
mu[1] = 1;
for(register int i = 2;i <= MX;++i)
{
if(!vis[i])
mu[prime[++cnt] = i] = mod - 1;
for(register int j = 1;j <= cnt && i * prime[j] <= MX;++j)
{
vis[i * prime[j]] = 1;
if(!(i % prime[j]))
break;
else
mu[i * prime[j]] = mod - mu[i];
}
}
scanf("%lld",&n);
for(register int i = 1;(long long)i * i <= n;++i)
{
long long s = 0;
for(register long long l = 1,r,lim = n / i / i;l <= lim;l = r + 1)
{
r = lim / (lim / l);
s = (s + (lim / l) % mod * (r - l + 1) % mod) % mod;
}
ans = (ans + s * mu[i] % mod) % mod;
}
printf("%lld\n",ans);
}