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