GCD（最大公约数） #
这里就不说GCD的定义，讲一些性质：
-
最小公倍数求法： (lcm(a,b) = \frac{ab}{gcd(a,b)})
-
区间的最大公约数
$$ Def. \quad GCD_{i=l}^{r} P_i= gcd(P_l, GCD_{i=l+1}^{r} P_i) \quad i.e. GCD_{i=r}^{r} P_i = P_r $$表示区间([l,r])中所有数的最大公约数。有如下性质：
- ( \forall k, s.t. k \in N, l \leq k \leq r, \quad GCD_{i=l}^{r} P_i = gcd(GCD_{i=l}^{k} P_i, GCD_{i=k+1}^{r} P_i)) 这个性质可以用在线段树，ST表存储区间GCD。区间和、最大、最小值也有这样的性质
- ( \forall r_1,r_2, s.t. r_1,r_2 \in N, l \leq r_1 \leq r_2, \quad GCD_{i=l}^{r_1} P_i \geq GCD_{i=l}^{r_2} P_i ) 这个性质常常用来区间二分。区间和、最大、最小值也有类似的性质，注意其中有的运算（和、最大值）要把不等号取反。
-
裴蜀定理
- 对于正整数(a,b)存在整数(x,y)使得(gcd(a,b)=ax+by)。
- 整数(a,b)互质的充要条件是存在整数(x,y)使得(ax+by=1)。
- (ax+by)必定是(gcd(a,b))的整数倍。
- 运用范围：数论问题求解；在长度为(n)的循环链表中进行定长为(k)的跳跃等。
异或 #
定义 #
在逻辑学中，逻辑算符异或（exclusive or）是对两个运算元的一种逻辑析取类型，符号为 (XOR) 或 (EOR) 或 (\oplus)（编程语言中常用^）。但与一般的逻辑或不同，异或算符的值为真仅当两个运算元中恰有一个的值为真，而另外一个的值为非真。转化为命题，就是：“两者的值不同。”或“有且仅有一个为真。”
(0 \oplus 0 = 0)
(0 \oplus 1 = 1)
(1 \oplus 0 = 1)
(1 \oplus 1 = 0)
性质 #
-
交换律：(A \oplus B = B \oplus A)
-
结合律：(A \oplus (B \oplus C) = (A \oplus B) \oplus C)
-
自反性：(A \oplus A = 0)。任何数与自身异或的结果都是0。
-
恒等律：(A \oplus 0 = A)。任何数与0异或的结果都是其自身。
-
逆元：( A \oplus B = C)，则 ( C \oplus B = A) 。可以用来“撤销”或“还原”之前的异或操作。
-
多次异或同一个数：对一个数进行偶数次异或操作结果不变，奇数次异或操作等于异或该数一次。
(e.g.)
- 偶数次：(A \oplus A \oplus A = A )；
- 奇数次：(A \oplus A \oplus A \oplus A = A \oplus A = 0);
(Co.) 每进行一次异或操作，就相当于对当前的 1 的个数的奇偶性进行一次翻转。可以利用这一性质对区间中奇数个数的奇偶性判断。
- (\bigoplus_{i = l} ^ {r} P[i] ) 是奇数 ( \iff P[l \sim r]) 有奇数个奇数。
- (\bigoplus_{i = l} ^ {r} P[i] ) 是偶数 ( \iff P[l \sim r]) 有偶数（包括0）个奇数。
-
区间异或和 可以通过预处理区间的前缀异或和，即(pre[i] = P[1] \oplus P[2] \oplus \cdots \oplus P[i])，由第五点性质得区间([l,r])的异或和： (\bigoplus_{i = l} ^ {r} P[i] = P[l] \oplus P[l+1] \oplus \cdots P[r-1] \oplus P[r] = pre[r] \oplus pre[l−1])。
贪心方法证明——交换法 #
贪心的交换论证思路 #
- 假设先选(i)再选(j)；
- 假设上述选法是对的，先选(i)再选(j)的代价小于先选(j)再选(i)，即满足(f(i,j) < f(j,i))（贡献等可反之，具体分析）；
- 化简(f(i,j) < f(j,i))，得到满足的条件。根据条件进行排序计算。
例题和解析 #
GDCPC2024 C #
题意：给一棵以1为根的树，每个点有权值(w_i)，找最优的dfs序（遍历子节点的顺序），求( max(\sum {p_i} {w_i}) )，其中(p)为dfs序。
如下图，当前根为(rt),假设dfs时“以(i)为根的子树后选，以(j)为根的子树先选”是最优的顺序，则有贡献( (siz[rt]−1−siz[i])∗f[i]+(siz[rt]−1−siz[i]−siz[j])∗f[j] )，其中(siz)表示子树大小，(f)表示子树权值和。
交换一下顺序，若先选(i)再选(j)，则有贡献( (siz[rt]−1−siz[j])∗f[j]+(siz[rt]−1−siz[j]−siz[i])∗f[i] )，展开后发现不同项为( −siz[i]∗f[j]>−siz[j]∗f[i]),即(\frac{siz[i]}{f[i]}<\frac{siz[j]}{f[j]} )，按照这个顺序选择子树即可。
