|
不妨设 \( n \leq m \)。 那原式： $= \sum_{i = 1} ^ n (n \bmod i) \times \sum_{j = 1} ^ m (m \bmod j) - \sum_{i = 1} ^ n (n \bmod i) \times (m \bmod i)$
$= \sum_{i = 1} ^ n \left( n - \left\lfloor \frac{n}{i} \right\rfloor \times i \right) \times \sum_{j = 1} ^ m \left( m - \left\lfloor \frac{m}{j} \right\rfloor \times j \right) - \sum_{i = 1} ^ n \left( n - \left\lfloor \frac{n}{i} \right\rfloor \times i \right) \left( m - \left\lfloor \frac{m}{i} \right\rfloor \times i \right)$
$= \sum_{i = 1} ^ n \left( n - \left\lfloor \frac{n}{i} \right\rfloor \times i \right) \times \sum_{j = 1} ^ m \left( m - \left\lfloor \frac{m}{j} \right\rfloor \times j \right) - \sum_{i = 1} ^ n \left( nm - n \times i \times \left\lfloor \frac{m}{i} \right\rfloor - m \times i \times \left\lfloor \frac{n}{i} \right\rfloor + i ^ 2 \times \left\lfloor \frac{n}{i} \right\rfloor \times \left\lfloor \frac{m}{i} \right\rfloor \right)$
显然对这 3 坨数论分块就可以了
题目3668 [清华集训 2012] 模积和
AAAAAAAAAA
 7
2 条 评论
2025-09-25 20:59:41
|
|
|
最小割必刷题！
首先我们先把棋盘看作二分图黑白染色，比如我们可以把横纵坐标加起来为奇数的看作黑，偶数看作白。
考虑到一个黑色节点只会对它四周的节点产生影响，不难想到我们直接把把源点往所有黑点连边权为这个点在棋盘上的数的边，白点同理，只是往汇点连边，然后相邻的方格之间连无穷大的边，这样这些边就不会被算在割边中。
那我们对于舍弃一个点，就是把这个点往源点或汇点的边割掉，dinic跑最小割即可。（ISAP不会写QAQ)
题目734 [网络流24题] 方格取数问题
AAAAAAAAAAA
7
1 条 评论
2025-09-25 20:49:45
|
|
|
一道好题。
这是一个树形结构，我们可以先拍成 $dfn$ 序，然后对于每个星球，本质上就是在其子树内区间再 删去一些小子树 所构成的一些区间，因为最多 $n$ 个操作，所以区间最多 $\mathcal{O}(n)$ 个，线段树分治，把这些区间插入，然后我们考虑如何求答案。
$y,z$ 是没用的，最终答案即为 $(x_0 - x)^2 + c$，拆开得 $- 2x_0x + {x_0}^2 + x^2 + c$。
我们考虑斜率优化，在看这个式子 $s = - 2x_0x + {x_0}^2 + x^2 + c$，移项得 $x^2 + c = 2x_0x - {x_0}^2 + s$，即点 $(x,x^2 + c)$ 斜率为 $2x_0$，维护下凸包即可，若二分则复杂度是 $\mathcal{O}(n\log^2{n})$，只需将 $x$ 与斜率 $x_0$ 都从小到大排序，我们可以利用单调栈达成 $\mathcal{O}(n\log{n})$ 的复杂度。
题目2305 [CTSC 2016]时空旅行
AAAAAAAAAAAAAAAAAAAA
10
评论
2025-08-11 18:37:14
|
|
|
http://218.28.19.228:8081/cogs/index.php书架二题解
|
|
|
COGS 1825 [USACO Jan11]道路与航线由于 $T \leq 25000,R+P \leq 100000$ ，优先考虑SPFA，
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > v[25005];
int d[25005];
bool vis[25005];
int p[25005];
int T, R, P, S;
void SPFA(int s) {
memset(d, 0x3f, sizeof(d));
memset(vis, 0, sizeof(vis));
memset(p, 0, sizeof(p));
queue<int> q;
q.push(s);
vis[s] = true;
d[s] = 0;
while (!q.empty()) {
int x = q.front();
q.pop();
vis[x] = 0;
for (int i = 0; i < v[x].size(); i++) {
if (d[v[x][i].first] > d[x] + v[x][i].second) {
d[v[x][i].first] = d[x] + v[x][i].second, p[v[x][i].first] = x;
if (!vis[v[x][i].first]) q.push(v[x][i].first), vis[v[x][i].first] = true;
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> T >> R >> P >> S;
for (int i = 1; i <= R; i++) {
int a, b, c;
cin >> a >> b >> c;
v[a].push_back(make_pair(b, c));
v[b].push_back(make_pair(a, c));
}
for (int i = 1; i <= P; i++) {
int a, b, c;
cin >> a >> b >> c;
v[a].push_back(make_pair(b, c));
}
SPFA(S);
for (int i = 1; i <= T; i++) {
if (d[i] == 0x3f3f3f3f) cout << "NO PATH" << endl;
else cout << d[i] << endl;
}
return 0;
}
最终评测T两个点，考虑换方法。 查看资料注意到SPFA有双端队列优化和优先队列优化，优先队列复杂度 $O(logn)$，故不考虑。双端队列优化思路是：将要加入的节点与队头比较，小于等于插到队头，大于则插到队尾，时间复杂度接近 $O(1)$。 重写代码
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > v[25005];
int d[25005];
bool vis[25005];
int p[25005];
int T, R, P, S;
void SPFA(int s) {
memset(d, 0x3f, sizeof(d));
memset(vis, 0, sizeof(vis));
memset(p, 0, sizeof(p));
deque<int> q;
q.push_back(s);
vis[s] = true;
d[s] = 0;
while (!q.empty()) {
int x = q.front();
q.pop_front();
vis[x] = 0;
for (int i = 0; i < v[x].size(); i++) {
if (d[v[x][i].first] > d[x] + v[x][i].second) {
d[v[x][i].first] = d[x] + v[x][i].second, p[v[x][i].first] = x;
//主要改动如下
if (!vis[v[x][i].first]) {
if (d[v[x][i].first] <= d[q.front()]) q.push_front(v[x][i].first);
else q.push_back(v[x][i].first);
vis[v[x][i].first] = true;
}
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> T >> R >> P >> S;
for (int i = 1; i <= R; i++) {
int a, b, c;
cin >> a >> b >> c;
v[a].push_back(make_pair(b, c));
v[b].push_back(make_pair(a, c));
}
for (int i = 1; i <= P; i++) {
int a, b, c;
cin >> a >> b >> c;
v[a].push_back(make_pair(b, c));
}
SPFA(S);
for (int i = 1; i <= T; i++) {
if (d[i] == 0x3f3f3f3f) cout << "NO PATH" << endl;
else cout << d[i] << endl;
}
return 0;
}
后记在知乎上看到文章关于SPFA的各种优化以及对应hack，可以参考（如何看待 SPFA 算法已死这种说法？ - 知乎 (zhihu.com)）。
题目1825 [USACO Jan11]道路与航线
2
评论
2025-07-01 10:55:47
|
|
|
$题目大意$ ${求}\sum_{i=1}^{n}\sum _{j=1}^{m}{lcm(i,j)} {且} 1\le n,m\le 1e7$ ${正解:}$ ${有}{lcm(i,j)=\frac{i\cdot j}{\gcd(i,j)}}$ ${所以原式为:}$ $ans(n,m)=\sum_{i=1}^{n}\sum _{j=1}^{m}{\frac{i\cdot j}{\gcd(i,j)}}$ $~\qquad\qquad =\sum_{i=1}^{n}\sum _{j=1}^{m}{ \sum_{d\mid i,d\mid j,\gcd(\frac{i}{d},\frac{j}{d})}{}{\frac{i\cdot j}{d}}}$ ${现在需要将d给提出来,默认}{n\le m,}{我们设}i=i'\cdot d,j=j'\cdot d,{则}i'=\frac{i}{d},j'=\frac{j}{d},将i,j替换进上式得:$ $ans(n,m)=\sum_{d=1}^{\min(n,m)}{\sum_{i'=1}^{\left \lfloor \frac{n}{d} \right \rfloor}{\sum_{j'=1}^{\left \lfloor \frac{m}{d} \right \rfloor}{[\gcd(i',j')=1]\cdot d\cdot i'\cdot j'}}}$ $~\qquad\qquad=\sum_{d=1}^{n}{d\cdot\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}{\sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor}{[\gcd(i,j)=1]\cdot i\cdot j}}}$ ${接着将d后面的部分再提出来考虑,化简枚举约数,运用莫比乌斯反演:} [\gcd(i,j)=1]=\sum_{d\mid gcd}{\mu{(d)}}:$ ${设} \ {g(n,m)}=\sum_{i=1}^{n}{\sum_{j=1}^{m}{[\gcd(i,j)=1]\cdot i\cdot j}}$ $~\qquad\qquad=\sum_{d=1}^{n}{\sum_{d\mid i}^{n}{\sum_{d\mid j}^{m}{\mu(d)\cdot i\cdot j}}}$ ${再设}\ i=i' \cdot d,j=j' \cdot d \ {带入,将}\mu{提出来}$ ${即}\ g(n,m)=\sum_{d=1}^{n}{\mu(d)}\cdot{d^{2}\cdot{\sum_{i=1}^{\left\lfloor \frac{n}{d} \right \rfloor}{\sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor}{i\cdot j}}}}$ $~\qquad\qquad = \sum_{d=1}^{n}{\mu(d)}\cdot{d^{2}}\cdot\frac{{\left \lfloor \frac{n}{d} \right \rfloor}\cdot ({\left \lfloor \frac{n}{d} \right \rfloor}+1)\cdot {\left \lfloor \frac{m}{d} \right \rfloor}\cdot({\left \lfloor \frac{m}{d} \right \rfloor}+1)}{4}$ ${最后将g(n,m)带入ans(n,m)中得:}$ $ans(n,m)=\sum_{d=1}^{n}{d}\cdot{g(\left\lfloor \frac{n}{d}\right\rfloor,\left\lfloor \frac{m}{d}\right\rfloor)}$ ${用数论分块求出来}~{g(n,m)}~{再用数论分块求出来}~{ans(n,m),}~{就在{\Theta(n+m)内}}{得到答案了}~{(∠・ω< )⌒★}$
题目1886 [国家集训队 2011] Crash的数字表格
AAAAAAAAAAAAAAAAAAAA
4
1 条 评论
2025-05-24 21:56:25
|
