脱产简记

· · 个人记录

主要整理了一些脱产和集训时做的题，写一下简要题解。

差分约束，一眼题。

题意：求 \sum_{i=1}^{n}gcd(i,n)

\sum_{i=1}^{n}gcd(i,n) =\sum_{d|n}\times \sum_{i=1}^{n}gcd(i,n)=d

然后除以 d 得

\sum_{d|n}\times \sum_{i=1}^{n \over d}gcd(i,\frac{n}{d})=1 =\sum_{d|n}\times \sum_{i}^{n\over d}\phi(i)

考虑枚举因子是 O(\sqrt{n}) 的。

如何快速求欧拉函数。

定理：

对于正整数 n

有 n=p_1^{c_1} \times p_2^{c_2}... \times p_k^{c_k}

则 \phi(n)=n \times (1-\frac{1}{p_1}) \times (1-\frac{1}{p_2}) \times ... \times (1-\frac{1}{p_k})

证明：

令正整数 n 有且仅有两个质因子 p,q

同时是 $p,q$ 的倍数的数有 $\frac{n}{pq}$ 个。 所以 $1 \sim n$ 中与 $n$ 互质的个数有 $n-\frac{n}{p}-\frac{n}{q}+\frac{n}{pq}

整理得

=n \times (1-\frac{1}{p}-\frac{1}{q}+\frac{1}{pq}) =n (1-\frac{1}{p})(1-\frac{1}{q})

结论得证。

由数学归纳法可知，结论成立。

最小割建模题。

首先虚拟源点和每个点连这个点的总价值，虚拟汇点和这个点连费用这个是显然的。

发现对于相邻的点，要连两点间的价值 \times 2。

因为考虑对于相邻的点，相同与不相同的贡献差是两倍的。

然后做完了。

01 分数规划。

不妨令 w_i=\{0/1\}，表示是否删掉第 i 组数。

有限制条件 \sum w_i \ge n-k

考虑如果一个答案 ans 满足条件，则有

\frac{\sum w_i \times a_i}{\sum w_i \times b_i} \ge ans

经过整理得

\sum w_i \times (a_i-ans\times b_i) \ge 0

那我们可以二分答案，然后判断。

判断可以从所有的 a_i-ans \times b_i 里面选 n-k 大的，然后判断这些数的和是否大于等于 0 即可。

复杂度 O(n \log ^2 n) 的。