BZOJ 4174 tty的求助：莫比烏斯反演求三重求和

題目簡介

計算 ∑_{n=1}^N ∑_{m=1}^M ∑_{k=0}^{m-1} ⌊(n*k + x)/m⌋ mod 998244353。N, M ≤ 500,000。

數學推導

固定 n,m，內層求和轉化：

∑_{k=0}^{m-1} ⌊(nk+x)/m⌋
= d*⌊x/d⌋ + n*m - n - m + d    (d = gcd(n,m))

雙重求和變為：

1/2 * [ S(N)S(M) - S(N)M - S(M)N + ∑_{d=1}^{min(N,M)} (d + 2d⌊x/d⌋) ∑_{k=1}^{min(N/d,M/d)} μ(k) ⌊N/(dk)⌋ ⌊M/(dk)⌋ ]

其中 S(n)=n(n+1)/2，μ 為莫比烏斯函數。線性篩預處理 μ，雙重枚舉 d 和 k，複雜度 O(N log N)。

代碼實現

#include <cstdio>
#include <iostream>
#define M 500500
#define MOD 998244353
using namespace std;
int n,m,x; long long ans;
int mu[M], prime[M], tot; bool notPrime[M];

void linearSieve() {
    mu[1]=1;
    for (int i=2;i> n >> m >> x;
    linearSieve();
    ans = (S(n)*S(m)%MOD - S(n)*m%MOD - S(m)*n%MOD + MOD)%MOD;
    if (n > m) swap(n,m);
    for (int d=1; d<=n; d++) {
        long long t = (d + 2LL*d*(x/d)%MOD)%MOD;
        for (int k=1; k*d<=n; k++)
            ans = (ans + t * mu[k]%MOD * (n/(d*k))%MOD * (m/(d*k))%MOD) % MOD;
    }
    cout << ans * ((MOD+1)/2) % MOD << endl;
    return 0;
}

複雜度分析

線性篩 O(M)，雙重循環 O(N log N)，N=5e5 約 1e7 次操作，極快。