BZOJ4174 tty的求助 <莫比乌斯反演>

Posted on Symbols count in article: 1.3k Reading time ≈ 5 mins.

Problem

tty的求助

Time  Limit:  20  Sec\mathrm{Time\;Limit:\;20\;Sec}
Memory  Limit:  256  MB\mathrm{Memory\;Limit:\;256\;MB}

Description

求∑n=1N∑m=1M∑k=0m−1⌊nk+xm⌋\sum_{n=1}^{N}\sum_{m=1}^{M}\sum_{k=0}^{m-1}\lfloor\frac{nk+x}{m}\rfloor，其中xx为实数。

Input

输入仅有一行。
第一行仅有两个正整数N,MN,M和一个实数xx。

Output

输出共一行，由于结果过大，所以请输出上式对998244353998244353取模的结果。

Sample Input

1
2 3 1

Sample Output

1
7

Explanation

当n=1,m=1n=1,m=1时，sum=1sum=1
当n=1,m=2n=1,m=2时，sum=1sum=1
当n=1,m=3n=1,m=3时，sum=1sum=1
当n=2,m=1n=2,m=1时，sum=1sum=1
当n=2,m=2n=2,m=2时，sum=1sum=1
当n=2,m=3n=2,m=3时，sum=2sum=2
所以答案是77

HINT

N,M≤5×105N,M\le5\times10^5，0<x≤1050<x\le10^5，xx精确到小数点后8位。

标签：莫比乌斯反演

Solution

Ans=∑n=1N∑m=1M∑k=0m−1⌊nk+xm⌋Ans=\sum_{n=1}^{N}\sum_{m=1}^{M}\sum_{k=0}^{m-1}\lfloor\frac{nk+x}{m}\rfloor\\

对于最后一次求和：

        ∑k=0m−1⌊nk+xm⌋=∑k=0m−1⌊nk−nk%m+x+nk%mm⌋=∑k=0m−1⌊nk%m+xm+nk−nk%mm⌋=∑k=0m−1⌊nk%m+xm⌋+∑k=0m−1nkm−∑k=0m−1nk%mm\begin{aligned} &\;\;\;\;\sum_{k=0}^{m-1}\lfloor\frac{nk+x}{m}\rfloor\\ &=\sum_{k=0}^{m-1}\lfloor\frac{nk-nk\%m+x+nk\%m}{m}\rfloor\\ &=\sum_{k=0}^{m-1}\lfloor\frac{nk\%m+x}{m}+\frac{nk-nk\%m}{m}\rfloor\\ &=\sum_{k=0}^{m-1}\lfloor\frac{nk\%m+x}{m}\rfloor+\sum_{k=0}^{m-1}\frac{nk}{m}-\sum_{k=0}^{m-1}\frac{nk\%m}{m}\\ \end{aligned}

先考虑前一项：
设d=gcd⁡(n,m)d=\gcd(n,m)，那么n⋅md≡0mod  mn\cdot\frac{m}{d}\equiv0\mod{m}。于是有n(k+md)%m=nk%m+nmd%m=nk%mn(k+\frac{m}{d})\%m=nk\%m+\frac{nm}{d}\%m=nk\%m，即可知nk%m=n(k%md)%mnk\%m=n(k\%\frac{m}{d})\%m。

        ∑k=0m−1⌊nk%m+xm⌋=∑k=0m−1⌊n(k%md)%m+xm⌋=mmd∑k=0md−1⌊n(k%md)%m+xm⌋=d∑k=0md−1⌊nk%m+xm⌋=d∑k=0md−1⌊nk%m+xm⌋\begin{aligned} &\;\;\;\;\sum_{k=0}^{m-1}\lfloor\frac{nk\%m+x}{m}\rfloor\\ &=\sum_{k=0}^{m-1}\lfloor\frac{n(k\%\frac{m}{d})\%m+x}{m}\rfloor\\ &=\frac{m}{\frac{m}{d}}\sum_{k=0}^{\frac{m}{d}-1}\lfloor\frac{n(k\%\frac{m}{d})\%m+x}{m}\rfloor\\ &=d\sum_{k=0}^{\frac{m}{d}-1}\lfloor\frac{nk\%m+x}{m}\rfloor\\ &=d\sum_{k=0}^{\frac{m}{d}-1}\lfloor\frac{nk\%m+x}{m}\rfloor\\ \end{aligned}

对于kk取遍0d,dd,2dd,⋯ ,m−dd\frac{0}{d},\frac{d}{d},\frac{2d}{d},\cdots,\frac{m-d}{d}，nknk的值依次为nd⋅0,nd⋅d,nd⋅2d,⋯ ,nd⋅(md−1)d\frac{n}{d}\cdot 0,\frac{n}{d}\cdot d,\frac{n}{d}\cdot 2d,\cdots,\frac{n}{d}\cdot (\frac{m}{d}-1)d。由于nd\frac{n}{d}与⌊md⌋\lfloor\frac{m}{d}\rfloor互质，所以nd⋅k%m\frac{n}{d}\cdot k\%m一定取遍0,1,2,⋯ ,(md−1)0,1,2,\cdots,(\frac{m}{d}-1)，因而nk%mnk\%m一定取遍0,d,2d,⋯ ,(md−1)d0,d,2d,\cdots,(\frac{m}{d}-1)d。故而有

        ∑k=0m−1⌊nk%m+xm⌋=d∑k=0md−1⌊nk%m+xm⌋=d∑k=0md−1⌊kd+xm⌋=d∑k=0md−1⌊kd+x%m+x−x%mm⌋=d∑k=0md−1⌊kd+x%mm⌋+d⋅md⋅x−x%mm\begin{aligned} &\;\;\;\;\sum_{k=0}^{m-1}\lfloor\frac{nk\%m+x}{m}\rfloor\\ &=d\sum_{k=0}^{\frac{m}{d}-1}\lfloor\frac{nk\%m+x}{m}\rfloor\\ &=d\sum_{k=0}^{\frac{m}{d}-1}\lfloor\frac{kd+x}{m}\rfloor\\ &=d\sum_{k=0}^{\frac{m}{d}-1}\lfloor\frac{kd+x\%m+x-x\%m}{m}\rfloor\\ &=d\sum_{k=0}^{\frac{m}{d}-1}\lfloor\frac{kd+x\%m}{m}\rfloor+d\cdot\frac{m}{d}\cdot\frac{x-x\%m}{m}\\ \end{aligned}

又发现0≤kd+x%m<2m⇒0≤⌊kd+x%mm⌋<20\le kd+x\%m<2m\Rightarrow0\le\lfloor\frac{kd+x\%m}{m}\rfloor<2，故

        ∑k=0m−1⌊nk%m+xm⌋=d∑k=0md−1⌊kd+x%mm⌋+d⋅md⋅x−x%mm=d×(∑k=0md−1[kd≥m−x%m]+x−x%md)=d×(∑k=0md−1[k≥⌈m−x%md⌉]+x−x%md)=d×(⌊x%md⌋+⌊xd⌋−⌊x%md⌋)=d⌊xd⌋\begin{aligned} &\;\;\;\;\sum_{k=0}^{m-1}\lfloor\frac{nk\%m+x}{m}\rfloor\\ &=d\sum_{k=0}^{\frac{m}{d}-1}\lfloor\frac{kd+x\%m}{m}\rfloor+d\cdot\frac{m}{d}\cdot\frac{x-x\%m}{m}\\ &=d\times(\sum_{k=0}^{\frac{m}{d}-1}[kd\ge m-x\%m]+\frac{x-x\%m}{d})\\ &=d\times(\sum_{k=0}^{\frac{m}{d}-1}[k\ge\lceil\frac{m-x\%m}{d}\rceil]+\frac{x-x\%m}{d})\\ &=d\times(\lfloor\frac{x\%m}{d}\rfloor+\lfloor\frac{x}{d}\rfloor-\lfloor\frac{x\%m}{d}\rfloor)\\ &=d\lfloor\frac{x}{d}\rfloor\\ \end{aligned}

对于后两项：

∑k=0m−1nkm=n⋅m⋅(m−1)2m=nm−n2∑k=0m−1nk%mm=d∑k=0md−1kdm=m−d2\sum_{k=0}^{m-1}\frac{nk}{m}=\frac{n\cdot m\cdot(m-1)}{2m}=\frac{nm-n}{2}\\ \sum_{k=0}^{m-1}\frac{nk\%m}{m}=d\sum_{k=0}^{\frac{m}{d}-1}\frac{kd}{m}=\frac{m-d}{2}\\

将三项和前面两个求和连起来：

Let  Si=1+2+⋯+i=i×(i+1)2,Ans=∑n=1N∑m=1M(d⌊xd⌋+nm−n−m+d2)=∑n=1N∑m=1M(d⌊xd⌋+d2)+12SNSM−M2SN−N2SM=∑n=1N∑m=1M(d⌊xd⌋+d2)+12SNSM−M2SN−N2SM\begin{aligned} Let\;&S_i=1+2+\cdots+i=\frac{i\times(i+1)}{2},\\ Ans&=\sum_{n=1}^{N}\sum_{m=1}^{M}(d\lfloor\frac{x}{d}\rfloor+\frac{nm-n-m+d}{2})\\ &=\sum_{n=1}^{N}\sum_{m=1}^{M}(d\lfloor\frac{x}{d}\rfloor+\frac{d}{2})+\frac{1}{2}S_NS_M-\frac{M}{2}S_N-\frac{N}{2}S_M\\ &=\sum_{n=1}^{N}\sum_{m=1}^{M}(d\lfloor\frac{x}{d}\rfloor+\frac{d}{2})+\frac{1}{2}S_NS_M-\frac{M}{2}S_N-\frac{N}{2}S_M\\ \end{aligned}

对前面的和式做莫比乌斯反演：

        ∑n=1N∑m=1M(d⌊xd⌋+d2)=∑d=1min⁡(N,M)(d⌊xd⌋+d2)∑i=1⌊Nd⌋∑j=1⌊Md⌋[gcd⁡(i,j)=1]=∑d=1min⁡(N,M)(d⌊xd⌋+d2)∑i=1⌊Nd⌋∑j=1⌊Md⌋∑t∣i,jμ(t)=∑d=1min⁡(N,M)(d⌊xd⌋+d2)∑t=1min⁡(⌊Nd⌋,⌊Md⌋)μ(t)⌊Ntd⌋⌊Mtd⌋\begin{aligned} &\;\;\;\;\sum_{n=1}^{N}\sum_{m=1}^{M}(d\lfloor\frac{x}{d}\rfloor+\frac{d}{2})\\ &=\sum_{d=1}^{\min(N,M)}(d\lfloor\frac{x}{d}\rfloor+\frac{d}{2})\sum_{i=1}^{\lfloor\frac{N}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{M}{d}\rfloor}[\gcd(i,j)=1]\\ &=\sum_{d=1}^{\min(N,M)}(d\lfloor\frac{x}{d}\rfloor+\frac{d}{2})\sum_{i=1}^{\lfloor\frac{N}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{M}{d}\rfloor}\sum_{t|i,j}\mu(t)\\ &=\sum_{d=1}^{\min(N,M)}(d\lfloor\frac{x}{d}\rfloor+\frac{d}{2})\sum_{t=1}^{\min(\lfloor\frac{N}{d}\rfloor,\lfloor\frac{M}{d}\rfloor)}\mu(t)\lfloor\frac{N}{td}\rfloor\lfloor\frac{M}{td}\rfloor\\ \end{aligned}

直接枚举dd数论分块即可，总时间复杂度约为O(2n−2n)O(2n-2\sqrt{n})。

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
#include <bits/stdc++.h>
#define MAX_N 500000
#define MOD 998244353
#define inv2 499122177
using namespace std;
typedef double dnt;
typedef long long lnt;
bool NotPri[MAX_N+5];    dnt x;
int n, m, cnt, pri[MAX_N+5], mu[MAX_N+5];
void init() {
    mu[1] = 1;
    for (int i = 2; i <= MAX_N; i++) {
        if (!NotPri[i]) pri[cnt++] = i, mu[i] = -1;
        for (int j = 0; j < cnt; j++) {
            if (i*pri[j] > MAX_N) break;
            NotPri[i*pri[j]] = true;
            if (i%pri[j]) mu[i*pri[j]] = -mu[i];
            else {mu[i*pri[j]] = 0; break;}
        }
    }
    for (int i = 2; i <= MAX_N; i++) mu[i] += mu[i-1];
}
lnt calc(int n, int m) {
    lnt ret = 0LL;
    for (int l = 1, r; l <= min(n, m); l = r+1)
        r = min(n/(n/l), m/(m/l)), 
        (ret += 1LL*(mu[r]-mu[l-1])*(n/l)%MOD*(m/l)%MOD) %= MOD;
    return ret;
}
int main() {
    scanf("%d%d%lf", &n, &m, &x), init();
    lnt sn = 1LL*n*(n+1)/2%MOD, sm = 1LL*m*(m+1)/2%MOD;
    lnt ans = sn*sm%MOD-1LL*m*sn%MOD-1LL*n*sm%MOD;
    for (int d = 1; d <= min(n, m); d++)
        (ans += (2LL*d*(lnt)(x/d)+d)%MOD*calc(n/d, m/d)%MOD) %= MOD;
    return printf("%lld\n", (ans*inv2%MOD+MOD)%MOD), 0;
}