Cauphenuny's blog

记录：

先看看 oi-wiki

记录一下比较复杂的插入部分。

求解满足 $a^x\equiv b\pmod p$ 的最小 $x$ （ $p$ 是质数）

定理

存在整数 $x$，$y$ 使得 $ax+by=\gcd(a,b)$

证明：

考虑求 $\gcd(a,b)$ 的过程，

$$\gcd(a,b)\to\gcd(b,r_1)\to\gcd(r_1,r_2)\to\cdots\to\gcd(r_{n-1},r_n)=1$$

acwing202. 最幸运的数字

P2398 GCD SUM

给定 $n$ ，求 $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\gcd(i,j)$ 数据范围：$n\leq10^5$

1. 写出 $\text{dp}$ 方程后，要先判断能不能使用斜优，即是否存在 $function(i)*function(j)$
   的项或者 $\frac{Y(j)-Y(j')}{X(j)-X(j')}$ 的形式。

2. 通过大小于符号或者 $b$ 中 $dp[i]$ 的符号结合题目要求 $(\min/ \max)$
   判断是上凸包还是下凸包，不要见一个方程就直接盲猜一个下凸。

3. 当 $X(j)$ 非严格递增时，在求斜率时可能会出现 $X(j_1)=X(j_2)$的情况，此时最好是写成这样的形式：return Y(j)>=Y(i)?inf:-inf，而不要直接返回 $inf$ 或者$-inf$，在某些题中情况较复杂，如果不小心画错了图，返回了一个错误的极值就完了，而且这种错误只用简单数据还很难查出来。

4. 注意比较 $k_0[i]$ 和 $slope(j_1,j_2)$ 要写规范，要用右边的点减去左边的点进行计算（结合 $(3)$来看，可防止返回错误的极值），如果用的代数法理解，写出了 (X(j2)-X(j1))*k0<=Y(j2)-Y(j1) 或(X(j2)-X(j1))*k0<=Y(j2)-Y(j1)，而恰巧 $j_1,j_2$又写反了，便会出现等式两边同除了负数却没变号的情况。当然用 $k_0$ 和 $\frac {Y(j_2)-Y(j_1)}{X(j_2)-X(j_1)}$ 进行比较是没有这种问题的。

5. 队列初始化大多都要塞入一个点 $P(0)$，比如 玩具装箱 $\text{toy}$，需要塞入$P(S[0],dp[0]+(S[0]+L)^2)$ 即 $P(0,0)$，其代表的决策点为 $j=0$。

6. 手写队列的初始化是 h=1,t=0，由于塞了初始点导致 $t$ 加 $1$，所以在一些题解中可以看到 h=t=1 甚至是 h=t=0，h=t=2 之类的写法，其实是因为省去了塞初始点的代码。它们都是等价的。

7. 手写队列判断不为空的条件是 h<=t ，而出入队判断都需要有至少 $2$ 两个元素才能进行操作。所以应是 h<t 。

8. 计算斜率可能会因为向下取整而出现误差，所以 $slope$ 函数最好设为 $long$ $double$ 类型。

9. 可能会有一部分的 $\text{dp}$ 初始值无法转移过来，需要手动提前弄一下，例如 摆渡车
   $\text{[P5017]}$。

10. 在比较两个斜率时，尽量写上等于，即 <= 和 >= 而不是 < 和 >。这样写对于去重有奇效（有重点时会导致斜率分母出锅），但不要以为这样就可以完全去重，因为要考虑的情况可能会非常复杂，所以还是推荐加上 3 中提到的特判，确保万无一失。

（题单）

1
2
3
4
5
6
7
8
9
10
11

玩具装箱 toy [HNOI2008] [P3195]
土地征用 Land Acquisition G [P2900]
征途 [SDOI2016] [P4072]
Cats Transport [CF311B]
摆渡车 [NOIP2018] [P5017]
仓库建设 [ZJOI2007] [P2120]
序列分割 [APIO2014] [P3648]
任务安排 2 [Loj10185] [Poj1180]
锯木厂选址 [CEOI2004] [P4360]
特别行动队 [APIO2010] [P3628]
国王饮水记 [NOI2016] [P1721]

• $\forall n>1$ ，$1$ ~ $n$中与 $n$ 互质的数的和为 $\dfrac{1}{2}n\times\varphi(n)$

  证明：$gcd(n,x)=gcd(n,n-x)$，所以与 $n$ 互质的数成对出现，平均数为 $n/2$ 。

• 若 p 为素数， $\varphi(p^k)=p^k(1-\dfrac{1}{p})=p^{k-1}(p-1)$

• $\varphi(n)=n(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})\ldots(1-\dfrac{1}{p_k})$

  证明：容斥

oi-wiki

给出 $n$ 个点 $P_i(x_i,y_i)$，将过这 $n$ 个点的最多 $n-1$ 次（为什么是 $n-1$ 次：因为可以构造出 $n$ 个线性方程，只能解出从常数项系数到 $n-1$ 次项的系数）的多项式记为 $f(x)$ ，求 $f(k)$ 的值。

link

转：link

题意:给你一颗树,每个点有一个权值,每条边可以留下或删除,问有多少种方案使得1所在的连通块中所有点的权值和恰好为 $K$.