题解 P2260 【[清华集训2012]模积和】
GKxx
2019-04-14 12:11:49
可以说是最近做的几道数学题里比较弱智的了
基本上就是[余数求和](https://www.luogu.org/problemnew/show/P2261)的加强版，没有设置什么障碍
$ans=\sum\limits_{i=1}^n\sum\limits_{j=1}^m(n\bmod i)(m\bmod j)-\sum\limits_{i=1}^{\min(n,m)}(n\bmod i)(m\bmod i)$
不妨记为$ans=a-b$，分别计算
$a=\sum\limits_{i=1}^n(n\bmod i)\sum\limits_{j=1}^m(m\bmod j)$
$=\sum\limits_{i=1}^n(n-i\lfloor\frac{n}{i}\rfloor)\sum\limits_{j=1}^m(m-j\lfloor\frac{m}{j}\rfloor)$
整除分块即可解决，就相当于把余数求和跑两遍
不妨设$k=\min(n,m)$那么
$b=\sum\limits_{i=1}^k(n-i\lfloor\frac{n}{i}\rfloor)(m-i\lfloor\frac{m}{i}\rfloor)$
$=\sum\limits_{i=1}^k(mn-mi\lfloor\frac{n}{i}\rfloor-ni\lfloor\frac{m}{i}\rfloor+i^2\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor)$
$=kmn-\sum\limits_{i=1}^k(mi\lfloor\frac{n}{i}\rfloor+ni\lfloor\frac{m}{i}\rfloor-i^2\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor)$
整除分块即可解决。
另外两个需要知道的公式：
$\sum\limits_{i=1}^ni=\frac{n(n+1)}{2}$
$\sum\limits_{i=1}^ni^2=\frac{n(n+1)(2n+1)}{6}$
前者使用的时候直接用$\text{long long}$就行了，但是后者需要求$6$的逆元，因为三个数相乘会爆$\text{long long}$。
```cpp
#include <cctype>
#include <cstdio>
#include <climits>
#include <algorithm>
template <typename T> inline void read(T& x) {
int f = 0, c = getchar(); x = 0;
while (!isdigit(c)) f |= c == '-', c = getchar();
while (isdigit(c)) x = x * 10 + c - 48, c = getchar();
if (f) x = -x;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
read(x); read(args...);
}
template <typename T> void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + 48);
}
template <typename T> inline void writeln(T x) { write(x); puts(""); }
template <typename T> inline bool chkmin(T& x, const T& y) { return y < x ? (x = y, true) : false; }
template <typename T> inline bool chkmax(T& x, const T& y) { return x < y ? (x = y, true) : false; }
typedef long long LL;
const LL mod = 19940417;
int n, m;
int inv6 = 3323403;
inline int s1(int l, int r) {
return 1ll * (l + r) * (r - l + 1) / 2 % mod;
}
inline int s2(int l, int r) {
auto f = [](int x) -> int { return 1ll * x * (x + 1) % mod * (2 * x + 1) % mod * inv6 % mod; };
return ((f(r) - f(l - 1)) % mod + mod) % mod;
}
inline int calc(int n) {
int ans = 1ll * n * n % mod;
for (int l = 1, r; l <= n; l = r + 1) {
r = n / (n / l);
ans = (ans - 1ll * s1(l, r) * (n / l) % mod + mod) % mod;
}
return ans;
}
int main() {
read(n, m);
int ans = 1ll * calc(n) * calc(m) % mod;
int mn = std::min(n, m);
ans = (ans - 1ll * mn * n % mod * m % mod + mod) % mod;
for (int l = 1, r; l <= mn; l = r + 1) {
r = std::min(n / (n / l), m / (m / l));
ans = (ans + 1ll * s1(l, r) * (1ll * n * (m / l) % mod + 1ll * m * (n / l) % mod) % mod) % mod;
ans = (ans - 1ll * s2(l, r) * (n / l) % mod * (m / l) % mod + mod) % mod;
}
writeln((ans % mod + mod) % mod);
return 0;
}
```