给定 $n. m, k$，求： $$ \sum_{i = 1}^n \sum_{j = 1}^m [\gcd(i, j) = k] $$ $n, m, k \leq 5 \times 10^4$
有 $T$ 组询问，$T \leq 5 \times 10^4$。
BZOJ 1011 Zap
给定 $n$，求： $$ \sum_{i = 1}^n \text{lcm}(i, n) $$ $1 \leq n \leq 10^6$
$T$ 组询问，$1 \leq T \leq 3 \times 10^5$
BZOJ 2705 LCMSum
给定 $n$，求：
$$ \sum_{i = 1}^n \gcd(i, n) $$
$1 \leq n \leq 2^{32}$
BZOJ 2705 Longge的问题 【SDOI 2010】
给定 $n, k$，求： $$ \sum_{i = 1}^n k\ \text{mod}\ i $$ $ 1 \leq n, k \leq 10^{9} $
BZOJ 1257 余数之和 【CQOI 2007】
余人国的国王想重新编制他的国家。
他想把他的国家划分成若干个省，每个省都由他们王室联邦的一个成 员来管理。
他的国家有 $n$ 个城市，编号为 $1..n$ 。一些城市之间有道路相连，任意两个不同的城市之间有且仅有一条直接或间接的道路。
为了防止管理太过分散，每个省至少要有 $B$ 个城市，为了能有效的管理，每个省最多只有 $3B$ 个城市。
每个省必须有一个省会，这个省会可以位于省内，也可以在该省外。
但是该省的任意一个城市到达省会所经过的道路上的城市（除了最后一个城市，即该省省会）都必须属于该省。
一个城市可以作为多个省的省会。
聪明的你快帮帮这个国王吧！
BZOJ 1086 王室联邦 【SCOI 2005】
莫队算法，用来处理一类 离线 区间查询问题，具有编程复杂度低，易于扩展的优点。
可以方便地扩展到树上，也可以以一定的代价支持修改。
作为一个生活散漫的人，小 Z 每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小 Z 再也无法忍受这恼人的找袜子过程，于是他决定听天由命……
具体来说，小 Z 把这 $N$ 只袜子从 $1$ 到 $N$ 编号，然后从编号 $L$ 到 $R$ 的袜子中随机选取，尽管小 Z 并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉小 Z ，他有多大的概率抽到两只颜色相同的袜子。当然，小 Z 希望这个概率尽量高，所以他可能会询问多个 $(L, R)$ 以方便自己选择。
BZOJ 2038 小 Z 的袜子 【国家集训队 2009】