今天遇到一个十分 Dark 的题目，让你求：
$$\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} lcm(i,j)$$
一共 $T$ 组数据，数据范围是：$T \leqslant 2 \ast 10^5, n \leqslant 3\ast 10^6$……
欧拉函数的应用：快速求解 1~n 中两两数字的最小公倍数
利用容斥原理求解 [a,b] 区间中与 n 互质的数字个数
先看这道丧心病狂的题目：HDU 4135 Co-prime。题目大意就是，有 $T$ 组询问，每组询问给你三个数：$a, b, c$，问你闭区间 $[a,b]$ 中有多少个数字与 $n$ 互质。数据范围是：$1 \leqslant A \leqslant B \leqslant 10^{15}$，$1 \leqslant N \leqslant 10^5$。
乍一看毫无头绪，仿佛怎么做都会超时……其实用容斥的想法就很容易了～
CodeForces 294E Shaass the Great：极其变态的树形 DP 与思维题
题目链接：CodeForces 294E Shaass the Great
这题真的太麻烦了……
八个放球问题方法总结（基础组合问题）
皮一下，N 个求放入 M 个盒子，总问题数量是 $C_2^1 \ast C_2^1 \ast C_2^1=8$ 个～
HDU 4045 Machine scheduling 题解：组合数+斯特林数
斯特林数的应用：HDU 6143 与 HDU 3625 题解
折线分割平面 题解
康托展开（Cantor Expansion）例题 + 略解
现在有N个数，分别为1到N，如果要问你这些数的所有排列中，从小到大数的第N个是多少，如何求解？
显然当N很小时直接写个模拟就可以了。但是这样写的时间复杂度至少是$A_N^N$，也就是$N!$，很容易超时。想想$13!$已经是6227020800了……有没有更快的方法呢？
BZOJ1002 轮状病毒 题解
POJ1723 士兵排队 题解
（POJ题目链接）
N soldiers of the land Gridland are randomly scattered around the country.
A position in Gridland is given by a pair (x,y) of integer coordinates. Soldiers can move - in one move, one soldier can go one unit up, down, left or right (hence, he can change either his x or his y coordinate by 1 or -1).