考前挂分是个好迹象，至少不像啥也不会那么绝望是不是/
A.城市间交通
第一眼整体二分+可撤销并查集，觉得有点难写，而且两个 \(\log\)。
再看一眼，发现最小生成树+倍增优秀单 \(\log\) 做法。
B.最小公倍数
第一眼这不是我们 P3911 最小公倍数之和 吗？
坏消息是忘了怎么莫反了。
于是写了个跟数学无关的两个 \(\log\) 普及组写法。
考虑设 \(f_{i,k}\) 为满足 \(\gcd(i,j)=k\) 的 \(j\) 的和，那么我们可以枚举 \(i\) 的倍数来求，但是 \(\gcd\) 可能不是 \(k\)，所以要减去 \(\gcd=2k,3k,\dots,nk\) 的情况，倒着 \(dp\) ，每次枚举 \(k\) 的因数提前减去就好。
点击查看代码
#include <bits/stdc++.h>
#define LL long long
#define pb push_back
using namespace std;
inline int read()
{
LL x = 0,f = 1;char ch = getchar();
while(!isdigit(ch)) (ch == '-') && (f = -1),ch = getchar();
while(isdigit(ch)) x = x*10+ch-48,ch = getchar();
return x*f;
}
const int N = 50010;
int c[N];
LL s[N],f[N];
vector < int > d[N];
int main()
{
for (int i = 1;i <= 5e4;i++)
for (int j = i;j <= 5e4;j += i) d[j].pb(i);
int n = read();
for (int i = 1;i <= n;i++) c[read()]++;
for (int i = 1;i <= 5e4;i++)
{
reverse(begin(d[i]),end(d[i]));
for (int j = i;j <= 5e4;j += i) s[i] += 1LL*j*c[j];
}
LL ans = 0;
for (int i = 1;i <= 5e4;i++)
{
for (int x : d[i])
{
f[x] += s[x];
for (int j = 1;j < d[x].size();j++) f[d[x][j]] -= f[x];
ans = ans+1LL*i/x*c[i]*f[x];
}
for (int x : d[i]) f[x] = 0;
}
cout << ans;
return 0;
}
C.衍生命题
应该没写挂，但是读错题了，写了个优秀的 线段树优化建图+线段树合并+可持久化线段树，拼在一块码量还挺小的。
所以代数之差里的代，为什么不是代数的代，而是第几代的代？
建一棵 \(\text{dfn}\) 序的线段树，每个节点维护一个按深度从小到大排序的 \(\text{vector}\)，相邻大数往小数连边优化建图就完了。
标签：ch,10.24,log,int,gcd,线段,getchar From： https://www.cnblogs.com/ZepX-D/p/18499652