JZOJ 5250.质数

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

于是就简单了。

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

代码:

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);
}