AC, Σndless

http://poj.org/problem?id=3148
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=255&page=show_problem&problem=1703

考察每条线段，对多边形进行梯形剖分。
按顺时针方向看，如果一条有向线段是向着 -x 轴的，那么它的下方形成的面积为负；如果一条有向线段是向着 +x 轴的，那么它的下方形成的面积为正。我们可以据此累加面积。
对每个梯形细条，分成三部分讨论，如下图：（只考察右边 1*5 的区域）

对于 ①，我们可从上往下算，每次减去前面的三角形面积就为当前梯形的面积。
对于 ②，用梯形面积减去 ① 中最后算出的三角形面积。
对于 ③，面积为 1 或 -1，这取决于这条线段的朝向。

http://codeforces.com/contest/475

D题 CGCDSSQ

大体思路是遍历一下原数组，当遍历到数 a[i] 时，计算 gcd(a[i], 从 a[j]「一路过来」的 gcd) (j<=i)。
注意这个计算过程是一个可以迭代的过程。
由于算出来的 gcd 有极多重复的值，而 a[i] 又很大，所以我们需要用一个 map 保存计算过的值及其个数，然后累加统计。
复杂度是 $O(nlog^{2}n)$

http://acm.hdu.edu.cn/showproblem.php?pid=4638

首先离线，按 r 从小往大排序。

由不等式 $(\sum_{i}x_i)^2>\sum_{i}x_i^2,\ x_i>0$ 可知，集合的个数越少越好。那么这道题的关键就在于如何「合并」集合。

为了说明的方便，举个例子：

设 ID 数组为 1,3,2,5,4，我们从左往右遍历，每读到一个数，树状数组当前位置就 +1，表示新增一个集合。

然后试着合并，看当前位置 i 前面有没有 a[i]-1 和 a[i]+1，有的话树状数组 pos[a[i]-1] 和 pos[a[i]+1] 就 -1，表示合并集合。

注意，遍历到最后一个数 4 的时候，我们把 3 和 5 所在位置各 -1（合并集合），但是先前遍历 2 的时候已经把 3 所在位置 -1 了，这对结果是没有影响的，因为查询的时候，3 会与 2 相互抵消。

http://acm.hdu.edu.cn/showproblem.php?pid=4630

比较能体现离线威力的一道题。
为了方便使用树状数组维护区间最值，我们从右往左遍历 a 数组，这样查询也要根据 l 从大往小排序。
对于 a[i] 这个数，对它的每个因子 m，我们找一个在 a[i] 右边的，离 a[i] 最近的，且同样有因子 m 的数，其下标为 j，则更新树状数组 j 位置的最值为 m。
为什么找最近的？因为离线查询按照 l 排序后有个天然的包含关系。
然后用树状数组查询区间最值就行。

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3122

此题的题解见我在知乎上的这个回答。

http://acm.hdu.edu.cn/showproblem.php?pid=4993

求出 $x_0,\ y_0$ 后，代入通解公式

解不等式。
复杂度 $O(\log{max(a,b)})$

http://acm.hdu.edu.cn/showproblem.php?pid=4992

先随便求一个n的原根r，然后n的原根就是 $r^t(mod \ n)$，这里 $gcd(t,\phi(n))=1$
原根的求法见 数论小记——原根、离散对数及 N 次剩余
有关上述定理的证明细节请参考《初等数论及其应用》9.1节。

原根：定义见 wiki，这里只补充讲解数 $n$ 的原根的求法.

首先我们肯定要从 $2$ 开始枚举 $\gcd(r,n)=1$ 的原根 $r$（或者rand()），关键在于怎么验证某一个数是不是一个原根：

1. 最暴力的方法就是暴力枚举 $[2,\phi(n)-1]$ 范围内的指数，看有是不是所有结果都不模 $n$ 余 $1$.
2. 优化：我们可以只枚举 $n$ 的因子，因为 $a$ 模 $n$ 的阶 $ord_{n}a$ 满足 $ord_{n}a\ |\ \phi(n)$.
   反证：若 $ord_{n}a\ \nmid\ \phi(n)$，则设 $\phi(n)=k\cdot ord_{n}a+r$，这里 $0<r<ord_{n}a$.
   那么 $a^{\phi(n)}\equiv a^{k\cdot ord_{n}a+r}\equiv (a^{ord_{n}a})^k\cdot a^r\equiv a^r\equiv 1(mod\ n)$，这与 $r<ord_{n}a$ 矛盾.
3. 继续优化：我们可以只枚举 $\phi(n)$ 的质因子 $p$，如果 $\forall p,\ r^{\frac{\phi(n)}{p}}\not \equiv 1(mod\ n)$，那么 $r$ 是模 $n$ 的原根.
   还是反证：在 $\forall p,\ r^{\frac{\phi(n)}{p}}\not \equiv 1(mod\ n)$ 的情况下，若 $r$ 不是模 $n$ 的原根，那必然有 $r^t\equiv 1(mod\ p),\ t<\phi(n)$.
   由 2 知 $t\ |\ \phi(n)$，故设 $\phi(n)=st,\ s>1$，再设 $p$ 是 $s$ 的一个因子，那同时 $p$ 也是 $\phi(n)$ 的一个因子，所以 $r^{\frac{\phi(n)}{p}}=(r^t)^{\frac{s}{p}}\equiv 1(mod\ p)$，矛盾.

这样求原根就会非常之快了.

未完待续。。。

http://acm.hdu.edu.cn/showproblem.php?pid=4990

既然分奇偶，就考察 $a_n$ 与 $a_{n-2}$ 的关系，稍微推一下即有：
$n$ 为奇数时，有 $a_n=1+4^1+4^2+...+4^{\frac{n-1}{2}}$
$n$ 为偶数时，有 $a_n=2*(1+4^1+4^2+...+4^{\frac{n-2}{2}})$
注意特判 m == 1

http://acm.hdu.edu.cn/showproblem.php?pid=4986

设期望为$E(n)$。此时再加入一个盒子，若盒子中的钥匙可以打开该盒子，则$E(n+1)=E(n)+1$，否则$E(n+1)=E(n)$。
前者发生的概率是$\dfrac{1}{n}$，后者发生的概率是$\dfrac{n-1}{n}$，所以最终$E(n+1)=E(n)+\dfrac{1}{n}$，所以此题就是求第$n$个调和数。