Hoodles!

斜率优化+平衡树

然而一看到就想到了cash，事实上这道题凸包上倍增就可以，写了个cdq跑得贼慢

Math!

找规律？

证明：

$\begin{aligned} 若&n\%k+m\%k>=k,有\lfloor \frac{n+m}{k}\rfloor-\lfloor \frac n k \rfloor-\lfloor \frac m k\rfloor=1\\原式 &=\sum_{k=1}^{n+m}\phi(k)\lfloor \frac{n+m}{k}\rfloor-\sum_{k=1}^{n}\phi(k)\lfloor \frac n k \rfloor-\sum_{k=1}^{m}\phi(k)\lfloor \frac m k\rfloor\\ &=\sum_{k=1}^{n+m}k-\sum_{k=1}^{n}k-\sum_{k=1}^{m}k\\ &=n*m\\ \end{aligned}$

Help!

求$\sum_{n=1}^N \sum_{m=1}^M \sum_{k=0}^{m-1}\lfloor \frac{nk+x} m\rfloor$

$\begin{aligned} 设f(n,m)&=\sum_{k=0}^{m-1}\lfloor \frac{nk+x}m\rfloor\\ &=\sum_{k=0}^{m-1}\lfloor \frac{nk\%m+x}m\rfloor+\lfloor \frac {nk-nk\%m}m\rfloor\\ &=\sum_{k=0}^{m-1}\lfloor \frac{nk\%m+x}m\rfloor+\frac {nk}m -\frac{nk\%m}{m} \end{aligned}\\$

分开计算每个部分：

$d=gcd(n,m)\\ \sum_{k=0}^{m-1}\frac{nk\%m}{m} = d*\sum_{k=0}^{\frac md+1} \frac{kd}m=\frac {m-d}2\\ \begin{aligned} 证明：&对于nk\%m,它是以\frac md为周期的,计算了d次，因为nk\%m=n(k+\frac md)\%m\\ &又因为nk\%m都是d的倍数,所以得证 \end{aligned}\\ \sum_{k=0}^{m-1}\frac{nk}m=\frac{n(m-1)}2\\ \sum_{k=0}^{m-1}\lfloor \frac{nk\%m+x}m\rfloor= d*\sum_{k=0}^{\frac md+1} \lfloor\frac{kd}m+\frac xm\rfloor\\ 根据具体数学P75,\sum_{i=0}^{m-1}\lfloor x+\frac im\rfloor=\lfloor mx\rfloor\\ 原式=d*\lfloor \frac xd\rfloor$

可得答案：

$\begin{aligned} an&s=\sum_{n=1}^N\sum_{m=1}^Mf(n,m)\\ &=\sum_{n=1}^N\sum_{m=1}^M\frac {d-m}2+\frac{n(m-1)}2+d*\lfloor \frac xd\rfloor\\ &=\frac{\frac{N*M*(N-1)*(M-1)}4-nm+\sum_{d=1}^Nd\sum_{i=1}^{\lfloor \frac Nd\rfloor}\mu (i)*\lfloor\frac N{id}\rfloor*\lfloor\frac M{id}\rfloor}2+\sum_{d=1}^Nd*\lfloor \frac xd \rfloor\sum_{i=1}^{\lfloor \frac Nd\rfloor}\mu (i)*\lfloor\frac N{id}\rfloor*\lfloor\frac M{id}\rfloor \end{aligned}$

最后反演,$O(n)$得答案

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
const int N = 500005;
typedef long long ll;
const ll mod = 998244353;
ll n, m, ans, sum[N];
int p[N], tot, mu[N], vis[N];
void Euler() {
	mu[1] = 1;
	for (int i = 2; i <= 500000; i++) {
		if (!vis[i]) p[++tot] = i, mu[i] = -1;
		for (int j = 1; j <= tot && i * p[j] <= 500000; j++) {
			int k = i * p[j];
			vis[k] = 1;
			if (i % p[j]) mu[k] = -mu[i];
			else {
				mu[k] = 0;
				break;
			}
		} 
	}
	for (int i = 1; i <= 500000; i++) mu[i] += mu[i - 1];
}
ll G(ll x, ll y) {
	ll rt = 0, i, j;
	for (i = 1; i <= x; i = j + 1){
		j = min(x / (x / i), y / (y / i));
		rt += (mu[j] - mu[i - 1]) * (x / i) % mod * (y / i) % mod;
		rt %= mod;
	}
	return rt;
}
int main() {
	int i, j, k;
	double x;
	scanf("%lld%lld%lf", &n, &m, &x);
	ans = n * m % mod * (n - 1) % mod * (m - 1) % mod * 748683265 % mod - n * m % mod + mod;
	ans %= mod;
	if (n > m) swap(n, m);
	Euler();
	for (i = 1; i <= n; i++) sum[i] = (sum[i - 1] + i + 2 * i * (ll)(x / i) % mod) % mod;
	for (i = 1; i <= n; i = j + 1) {
		j = min(n / (n / i), m / (m / i));
		ans += (sum[j] - sum[i - 1] + mod) % mod * G(n / i, m / i) % mod;
		ans %= mod;
	}
	ans *= 499122177;//rev 2
	ans %= mod;
	printf("%lld", ans);
}