题解 【P2260 [清华集训2012]模积和】

套路推式子题好像还挺无脑的啊。

规定 $n<m$。原式珂以等于这一坨。

$$(\sum\limits^n_{i=1}(n\operatorname{mod} i) )(\sum\limits^m_{j=1}(m\operatorname{mod} j))-\sum\limits^n_{i=1}((n\operatorname{mod} i)\times (m\operatorname{mod} i))$$

那么可以把减号左右两边的和式分别处理。先处理好搞的左边。按照这题的方法强行把模转化为除法然后用整除分块求解。那么 $\sum\limits^n_{i=1}n\operatorname{mod} i$ 实际上等于 $\sum\limits^n_{i=1}(n-\lfloor \frac{n}{i}\rfloor\times i)$。$\sum\limits^m_{j=1}m\operatorname{mod} j$ 一个道理。

现在处理右边的和式。

$$\begin{aligned} \sum\limits^n_{i=1}(n\operatorname{mod} i)\times (m\operatorname{mod} i)&=\sum\limits^n_{i=1}(n-\lfloor\frac{n}{i}\rfloor\times i)(m-\lfloor\frac{m}{i}\rfloor\times i)\\ &=\sum\limits^n_{i=1}nm-ni\lfloor\frac{m}{i}\rfloor-mi\lfloor\frac{n}{i}\rfloor+\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor i^2\\ &=n^2m-n\sum\limits^n_{i=1}i\lfloor\frac{m}{i}\rfloor-m\sum\limits^{n}_{i=1}i\lfloor\frac{n}{i}\rfloor+\sum\limits^n_{i=1}\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor i^2 \end{aligned}$$

把一个和式硬拆成三个和式有意思吗？

最后展开的式子，前两个和式朴素地整除分块即可，最后那个和式……我们好像确定了一个 $[l,r]$ 区间商都为 $k$ 后需要计算 $\sum\limits^r_{i=l}i^2$。

根据小学奥数知识，$\sum\limits^n_{i=1}i^2=\frac{n(n+1)(2n+1)}{6}$。所以前缀和一下 $\sum\limits^r_{i=l}i^2=\sum\limits^r_{i=1}i^2-\sum\limits^{l-1}_{i=1}i^2$，套公式即可。

#include <cstdio>
#define int long long

const int mod = 19940417;
inline int min(const int x, const int y) {return x < y ? x : y;}

int qpow(int a, int b) {
	int ret = 1LL;
	while (b) {
		if (b & 1) ret = ret * a % mod;
		a = a * a % mod;
		b >>= 1; 
	}
	return ret;
}

int calc(int n) {
	int ans = 0;
	ans = n * n;
	for (int l = 1, r; l <= n; l = r + 1) {
		r = n / (n / l);
		ans -= (n / l) * (r - l + 1) * (l + r) / 2;
	}
	ans = (ans % mod + mod) % mod;
	return ans;
}
int calc2(int n, int k) {
	int sum = 0;
	if (k > n) k = n;
	for (int l = 1, r; l <= k; l = r + 1) {
		r = min(n / (n / l), k);
		sum = (sum + (n / l) * (r - l + 1) * (l + r) / 2 % mod) % mod;
	}
	return sum;
}
int calc4(int n) {
	if (!n) return 0;
	int a[] = {n, n + 1, 2 * n + 1};
	for (int i = 0; i <= 2; ++ i)
		if (a[i] % 2 == 0) {a[i] /= 2; break;}
	for (int i = 0; i <= 2; ++ i)
		if (a[i] % 3 == 0) {a[i] /= 3; break;}
	return a[0] * a[1] % mod * a[2] % mod;
}
int calc3(int n, int m) {
	int sum = 0;
	for (int l = 1, r; l <= n; l = r + 1) {
		r = min(n / (n / l), m / (m / l));
		int k = (calc4(r) - calc4(l - 1) + mod) % mod;
		sum = (sum + (n / l) * (m / l) * k % mod) % mod;
	}
	return sum % mod;
}

signed main() {
	int n, m, ans;
//	printf("%lld", calc3(6, 10));
//	return 0;
	scanf("%lld%lld", &n, &m);
	if (n > m) n ^= m ^= n ^= m;
	ans = calc(n) * calc(m) % mod;
	ans = (ans - n * n % mod * m % mod) % mod;
	ans = (ans - calc3(n, m)) % mod;
	ans = (ans + n * calc2(m, n) % mod + m * calc2(n, m) % mod) % mod;
	printf("%lld", (ans + mod) % mod);
	return 0;
}