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

Problem

tty的求助

Description

求，其中为实数。

Input

输入仅有一行。
第一行仅有两个正整数和一个实数。

Output

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

Sample Input

2 3 1

Sample Output

7

Explanation

当时，
当时，
当时，
当时，
当时，
当时，
所以答案是

HINT

，，精确到小数点后8位。

标签：莫比乌斯反演

Solution

对于最后一次求和：

先考虑前一项：
设，那么。于是有，即可知。

对于取遍，的值依次为。由于与互质，所以一定取遍，因而一定取遍。故而有

又发现，故

对于后两项：

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

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

直接枚举数论分块即可，总时间复杂度约为。

Code

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