## 素数
#数学 #质数 #最大公因数
首先，对于两个相邻的质数 $a$ 和 $b$，在 $[a,b)$ 内的所有数的 $\cfrac{1}{u(i)v(i)}$ 都是 $\cfrac{1}{ab}$，而这个区间内一共有 $b-a$ 个数，因此这一段区间对答案的贡献为 $\cfrac{b-a}{ab}$。
不难发现这个式子特别像小学数学学过的裂项，可以变成 $\cfrac{1}{a}-\cfrac{1}{b}$。那么，如果有多个区间拼起来，如 ${} \cfrac{b-a}{ab}+\cfrac{c-b}{bc}+\cdots+\cfrac{z-y}{yz} {}$，最后又会变成什么呢？中间的项将会全部消掉，因此只剩下了 $\cfrac{1}{a}-\cfrac{1}{z}$。
因此对于询问 $n$，我们可以找到小于等于 $n$ 的最大质数 $p$，此时 $[2,p)$ 内的数对答案的贡献就是 $\cfrac{1}{2}-\cfrac{1}{p}$ 了。但是我们还有一段 $[p,n]$ 的贡献没有考虑。若大于 $n$ 的下一个质数为 $r$，那么这一段内单个元素的贡献就为 $\cfrac{1}{pr}$，总共贡献 $\cfrac{r-n+1}{pr}$。因此我们只需要进行分数加减运算就行了。
- [!] 注意像我这种暴力同分相加再约分的，需要开 $128$ 位整数。
由于 $10^9$ 范围内质数的个数大约为 $5\times 10^7$，因此寻找上、下一个质数的速度都是很快的，暴力根号判别即可。
```cpp
#include <fstream>
using namespace std;
using LL = long long;
ifstream cin("prime.in");
ofstream cout("prime.out");
LL t, n, prv, nxt;
bool isPrime(LL n) {
for (LL i = 2; i * i <= n; i++) {
if (n % i == 0) {
return 0;
}
}
return 1;
}
__int128_t gcd(__int128_t a, __int128_t b) {
return !b ? a : gcd(b, a % b);
}
void add(__int128_t &a, __int128_t &b, LL c, LL d) {
LL g = gcd(c, d);
c /= g;
d /= g;
a = a * d + c * b;
b = b * d;
if (!a) {
b = 1;
return;
}
g = gcd(a, b);
a /= g;
b /= g;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
for (cin >> t; t; t--) {
cin >> n;
for (prv = n; !isPrime(prv); prv--) { }
for (nxt = n + 1; !isPrime(nxt); nxt++) { }
__int128_t a = 1, b = 2;
add(a, b, -1, prv);
add(a, b, n - prv + 1, nxt * prv);
cout << (LL)a << '/' << (LL)b << '\n';
}
return 0;
}
```
## 秘密通道
#广度优先搜索 #优先队列
首先打开窗口一定是要用的，否则完全没必要打开。因此对于一个格子，它除了可以上下左右移动以外，还可以对于上下左右的方向，选择两个方向打开窗口，往其中一个地方走过去传送，这个可以通过 $4\times 4$ 枚举实现。
状态的话，起点唯一，因此到一个地方肯定是代价越小越好。
- [n] 这时我们就觉得可能会挂，原因是传送之后不一定需要开两个窗口，只需要往其中一个地方开窗口然后用上次传送过来的那个窗口传送。不过实际上可以看作往那个窗口再次放置窗口，然而比赛时的我完全没有想这么多因此就进行了特殊处理，还增加了一个 0/1 状态（是否刚传送）。这是很明显的状态冗余。
于是思路就很清晰了。
1. 预处理每个点往四个方向分别能打到哪些地方；
2. 跑 bfs，两种移动方式：
- 往相邻各自走；
- 选择一个方向放置传送门并走过去传送，选择另一个方向作为传送终点
3. 输出答案
- [!] 对于第二种移动方式，增加的代价不一定为 $1$，因此需要使用优先队列而非普通队列进行 BFS。我就是这个挂成了 $60$ 分（`push` 过多导致 MLE）。
```cpp
#include <fstream>
#include <utility>
#include <queue>
using namespace std;
const int kMaxN = 505, kD[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
ifstream cin("portal.in");
ofstream cout("portal.out");
struct Node {
int x, y, d;
Node(int x, int y, int d):
x(x), y(y), d(d) { }
friend bool operator<(const Node &a, const Node &b) {
return a.d > b.d;
}
};
int d[kMaxN][kMaxN], f[kMaxN][kMaxN], n, m, sx, sy, ex, ey;
pair<int, int> p[kMaxN][kMaxN][4];
priority_queue<Node> q;
char a[kMaxN][kMaxN];
void record(int x, int y, int dis) {
if (x < 1 || x > n || y < 1 || y > m || a[x][y] == '#' || dis >= d[x][y]) {
return;
}
d[x][y] = dis;
q.emplace(x, y, dis);
}
int calc(int x, int y, const pair<int, int> &p) {
return abs(x - p.first) + abs(y - p.second);
}
void bfs(int x, int y) {
fill(d[0], d[0] + kMaxN * kMaxN, 1e9);
for (q.emplace(x, y, 0), d[x][y] = 0; q.size(); q.pop()) {
auto t = q.top();
if (f[t.x][t.y]) {
continue;
}
f[t.x][t.y] = 1;
for (auto i : kD) {
record(t.x + i[0], t.y + i[1], d[t.x][t.y] + 1);
}
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
record(p[t.x][t.y][j].first, p[t.x][t.y][j].second, d[t.x][t.y] + calc(t.x, t.y, p[t.x][t.y][i]) + 1);
}
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
if (a[i][j] == 'C') {
sx = i, sy = j;
} else if (a[i][j] == 'F') {
ex = i, ey = j;
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i][j] == '#') {
continue;
}
for (int k = 0; k < 4; k++) {
int x = i, y = j;
for (; a[x][y] != '#'; x += kD[k][0], y += kD[k][1]) { }
x -= kD[k][0], y -= kD[k][1];
p[i][j][k] = {x, y};
}
}
}
bfs(sx, sy);
int ans = d[ex][ey];
cout << (ans != 1e9 ? to_string(ans) : "nemoguce") << '\n';
return 0;
}
```
## 宝可梦
#区间dp #排序 #前缀和 #二分
每个宝可梦只能拾取一次，因此可以想到状压，但是 $m\le 100$ 很显然不能搞。不过我们可以发现最优情况下的已拾取的宝可梦一定是一段区间，因为走往边界时中间的宝可梦都可以顺便捡上。
$n$ 很大，但是宝可梦 $m$ 很少，所以可以对位置进行离散化。移动一定是奔着宝可梦去的，因此不必记录实际位置只需要记录在那个宝可梦的位置上。
我们可以想到区间 DP。由于宝可梦的拾取有时间限制，而且时间本身只有 $2000$ 的值域，因此可以直接加入维度。设 $dp_{i,j,k,p}$ 表示当前时刻为 $i$，已拾取了 $[j,k]$ 内的所有宝可梦，当前在第 $p$ 个宝可梦身上。然后发现空间炸了。
仔细思考，发现 $p$ 一定是在 $j$ 或者 $k$ 上，因为转移一定是会扩大区间的，而扩大区间的原因就是 $p$，所以 $p$ 一定在边界上。所以这一维可以直接变成 $0/1$。
然后是转移。很多人会觉得一次可以扩大区间很多，但是实际上只需要扩大一次（左边或右边），因为路上的贡献会累加起来。
至于多个宝可梦有相同的 $a_i$，可以离散化后分位置存入 `vector`，然后单个 `vector` 内以时间排序，做前缀和。转移的时候就二分第一个大于等于转移过去后的时刻的宝可梦限时，然后用前缀和做差即可。
时间复杂度 $\mathcal O(Tm^2\log_2 n)$。需要注意的是：
1. 内存很紧张，要卡着最大值开，例如把时间维度开成 $3000$ 就会导致 MLE；
2. 就算 DP 数组没有炸也占用超过 $160~\text{MB}$，其它数组尽量注意空间；
3. DP 数组不要开 `long long` 也不需要，否则同样 MLE。
```cpp
#include <fstream>
#include <algorithm>
#include <utility>
#include <vector>
#include <ctime>
using namespace std;
const int kMaxM = 105, kMaxT = 2e3 + 5;
ifstream cin("go.in");
ofstream cout("go.out");
struct Node {
int sum, t;
Node(int sum, int t):
sum(sum), t(t) { }
friend bool operator<(const Node &a, const Node &b) {
return a.t < b.t;
}
};
int dp[kMaxT][kMaxM][kMaxM][2], a[kMaxM], b[kMaxM], t[kMaxM], val[kMaxM], n, k, m, cnt, ans;
vector<Node> v[kMaxM];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k >> m;
val[++cnt] = k;
for (int i = 1; i <= m; i++) {
cin >> a[i] >> b[i] >> t[i];
val[++cnt] = a[i];
}
sort(val + 1, val + cnt + 1);
n = unique(val + 1, val + cnt + 1) - val - 1;
for (int i = 1; i <= m; i++) {
a[i] = lower_bound(val + 1, val + n + 1, a[i]) - val;
v[a[i]].emplace_back(b[i], t[i]);
}
for (int i = 1; i <= n; i++) {
if (v[i].empty()) {
continue;
}
sort(v[i].begin(), v[i].end());
for (int j = 1; j < v[i].size(); j++) {
v[i][j].sum += v[i][j - 1].sum;
}
}
fill(dp[0][0][0], dp[0][0][0] + kMaxT * kMaxM * kMaxM * 2, -1e9);
k = lower_bound(val + 1, val + n + 1, k) - val;
ans = max(ans, dp[1][k][k][0] = v[k].size() ? v[k].back().sum : 0);
for (int i = 1; i <= 2e3; i++) {
for (int j = 1; j <= n; j++) {
for (int k = j; k <= n; k++) {
for (int p = 0; p <= 1; p++) {
if (dp[i][j][k][p] == -1e9) {
continue;
}
// 0: Left 1: Right
int x = p ? val[k] : val[j];
if (j > 1 && i + (x - val[j - 1]) <= 2e3) {
int t = i + (x - val[j - 1]);
auto it = lower_bound(v[j - 1].begin(), v[j - 1].end(), Node{0, t});
ans = max(
ans,
dp[t][j - 1][k][0] = max(
dp[t][j - 1][k][0],
dp[i][j][k][p] + v[j - 1].back().sum - (it != v[j - 1].begin() ? prev(it)->sum : 0)
)
);
}
if (k < n && i + (val[k + 1] - x) <= 2e3) {
int t = i + (val[k + 1] - x);
auto it = lower_bound(v[k + 1].begin(), v[k + 1].end(), Node{0, t});
ans = max(
ans,
dp[t][j][k + 1][1] = max(
dp[t][j][k + 1][1],
dp[i][j][k][p] + v[k + 1].back().sum - (it != v[k + 1].begin() ? prev(it)->sum : 0)
)
);
}
}
}
}
}
cout << ans << '\n';
return 0;
}
```
## 世界树
#树形dp
首先题目中都明确说明换根两个字了，这提醒我们是换根 DP。
先考虑如果选好根了答案怎么算。题面跟托石一样就不用看了，简单来说就是一条边的实际边权等于这条边的边权减去边上作为父亲的结点的点权，然后对根到任意一个节点的路径上实际边权和求和。
可以设计 DP 状态。设 $dp_i$ 表示 $i$ 子树内的答案，那么对于当前节点肯定要把所有儿子的 DP 值之和都加起来。然后是到儿子 $s$ 那条边的贡献，会有 $siz_i$ 次路过，因此可以得到转移方程
$
dp_x=\sum_{i\in son_x}(dp_i+siz_i\times(w_{(x,i)}-a_x))
$
接下来考虑换根。如果我们把根从 $u$ 换到 $v$，贡献会发生什么？对于 $v$ 子树内的节点，到根的路径长度都会减掉原来 $w_{(u,v)}$ 的实际边权；对于其它所有节点，到根的路径长度都会增加新的 $w_{(v,u)}$ 的实际边权。设 $f_i$ 表示为以 $i$ 作为根的答案，可以得到转移方程
$
f_i=f_x-siz_i\times(w_{(u,v)}-a_u)s+(n-siz_i)\times(w_{(v,u)}-a_v)~(i\in son_x)
$
时间复杂度 $\mathcal O(n)$。注意开 `long long`。
```cpp
#include <fstream>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
using LL = long long;
const LL kMaxN = 1e6 + 5;
ifstream cin("yggdrasil.in");
ofstream cout("yggdrasil.out");
LL a[kMaxN], dp[kMaxN], siz[kMaxN], ans[kMaxN], n;
vector<pair<LL, LL>> e[kMaxN];
void dfs1(LL x, LL f) {
siz[x] = 1;
for (auto i : e[x]) {
if (i.first != f) {
dfs1(i.first, x);
dp[x] += dp[i.first] + siz[i.first] * (i.second - a[x]);
siz[x] += siz[i.first];
}
}
}
void dfs2(LL x, LL f) {
for (auto i : e[x]) {
if (i.first == f) {
continue;
}
ans[i.first] = ans[x] - siz[i.first] * (i.second - a[x]) + (n - siz[i.first]) * (i.second - a[i.first]);
dfs2(i.first, x);
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (LL i = 1; i <= n; i++) {
cin >> a[i];
}
for (LL i = 1, u, v, w; i < n; i++) {
cin >> u >> v >> w;
e[u].emplace_back(v, w);
e[v].emplace_back(u, w);
}
dfs1(1, 0);
ans[1] = dp[1];
dfs2(1, 0);
cout << min_element(ans + 1, ans + n + 1) - ans << '\n' << *min_element(ans + 1, ans + n + 1) << '\n';
return 0;
}
```