Lost Cows（暴力/线段树）
描述传送门：POJ 2182 - Lost Cows
有一些奶牛，从 $1$ 到 $N$ 编号，现在这些奶牛站成一行，但是没有按顺序，我们只知道一个条件：对于某一只奶牛，站在它前面并且编号比它小的奶牛的数量。要求计算出每只奶牛的编号。
思路根据题意，我们考虑最后一只奶牛（设为 $N$），我们知道站在它前面的并且编号比它小的奶牛的数目（设为 $Pre[N]$ ），因为所有的其他奶牛已经都在它前面了，所以 $Pre[N]$ 也就是所有奶牛中编号比它小的数目，那么这最后一只奶牛，编号就是 $Pre[N]+1$ 。
然后从后往前推，第 $N-1$ 只奶牛，站在它前面的编号比它小的奶牛数目是 $Pre[N-1]$ ，因为我们是从后往前推的，那么站在这第 $N-1$ 只奶牛后面的，编号肯定都已经确定了，那么从编号 $1$ 开始往后查找，第 $Pre[N-1]+1$ 个没有被确定的编号，就是它的编号。以此类推，直到所有奶牛的编号都确定下来。
因为题目数据范围较小，只有 $8000$， $O(n^2)$ 的暴力算法就可以过了，但是秉着学习的态度，还是用线段树解了一发，万一遇到数据很大的类似题目呢~！
...
Apple Tree（DFS序+树状数组）
传送门： POJ 3321 - Apple Tree
题目大意：给你一棵树（不是二叉树，多少个枝干都有可能），树的形式以结点关系描述的形式给出，比如给你 $u$ 和 $v$，表示编号为 $v$ 的结点是编号为 $u$ 的结点的子结点。每个结点上有一个苹果，有两个操作 C 和 Q ：操作 C ：告诉你一个结点，如果这个结点当前有苹果，那就把它摘下来，如果没有，那这个结点就长出一个苹果。操作 Q ：同样是告诉你一个结点，问你以这个结点为根的子树上一共有多少个苹果。
解题思路：
遇到这类有频繁的单点修改和区间查询操作的题目，一般首先想到的都是树状数组或者线段树来解，这个题目也没例外。
对于这个题，给出的是结点的关系，那么我们就可以用 DFS序 得到这个树的遍历序列，我们知道，DFS序有一个特殊的性质，就是一个结点的子树一定是在一个连续的区间内的，比如题目样例里面的数据，DFS序为 “122331”，对于以结点 1 为根的子树，每一个结点的进入与离开时间，全都在结点 1 的进入时间和离开时间之间。
我们用树状数组来维护DFS序列，对于操作 C ，我们只要把DFS序列中这个结点的进入和离开的序列 ...
想要的 GitHub ID 被注册了怎么办？
作为一名计算机专业的学生，加入 GitHub 已经有一段时间了。
我想很多人和我一样，想要某一个 id 却苦于已被注册，比如我想要的，就是我姓名的全拼 id “gukaifeng”。
因为我的全拼 id 被注册了，所以只能用其他的，但换来换去，也始终没能有一个称心的 id。
我本想去联系我的名字全拼 id 的持有人，但是到了那个主页后看到的画面是这样子的：
这直接断了我想联系这个人的念头。。。
气愤！占着 XXX ( GitHub id ) 不 XXX ( 干正事 ) ！
…
后来无意间听说，GitHub 其实是有闲置 id 的处理方案的，允许用户去申请的。
惊了个呆！这简直就是为我量身定制的啊！
于是开始 Google 方案，花了 1 个小时，并没有找到什么有卵用的东西。。。
想了想，也许可以尝试下 Contact GitHub 的呀！说做就做！当然了结果是成功啦，不然也不会有这篇博客了，下面记录下过程，给有同样想法的小伙伴借鉴。
1. 要先确认下，这个方法也是有前提条件的，就是你想要的这个 id 虽被注册了，但是处于一个长期闲置的状态，就像我上面发的图的那样。如果你想要的 id ...
Trailing Zeroes (III)（算术基本定理+二分查找）
传送门：LightOJ 1138 - Trailing Zeroes (III)
题目大意：
给你一个数 $Q$，问你，阶乘结果末尾有 $Q$ 个 $0$ 的数，最小是多少。
$1\leqslant Q\leqslant 1e8$
解题思路：
我们先来考虑如何计算一个正整数的阶乘结果末尾 $0$ 的个数。
如果将一个正整数因式分解，那么其末尾的 $0$ 必然可以分解为 $2\times 5$，也就是说，因子中每一对 $2$ 和 $5$ 就对应着末尾的一个 $0$，因为 $2$ 肯定比 $5$ 多，所以我们只要统计因子中有多少个 $5$ 就是结果了。根据算术基本定理中，性质(5)：$n!$ 的素因子分解中的素数 $p$ 的幂为 $[\frac{n}{p}]+[\frac{n}{p^2}]+[\frac{n}{p^3}]+\cdots$我们把 $p=5$ 代入，计算出结果即为所求。代码如下：
12345678910int trailingZeroes(int n) { int cnt = 0; long long p = 5; while (n / p) ...
Prime Test（Miller-Rabin素数测试+Pollard rho整数分解）
传送门：POJ 1811 - Prime Test
题目大意：
给你一个数 $N$ $(2\leqslant N\leqslant 2^{54})$ 判断 $N$是否为素数，是的话直接输出 “Prime”，不是的话输出最小质因数。
解题思路：
看到这个数据范围，我就知道，常规算法肯定是行不通了=。=！所以就得用Miller-Rabin素数测试来判断是否是素数了，然后如果是的话，直接输出”Prime”就行了，不是就用Pollard rho整数分解方法算质因数，再找出所有质因数中最小的那一个就好了。要注意的地方也就是在进行Miller-Rabin素数测试的时候，要使用二次探测定理，排除卡迈克尔数（一个合数 $n$，若对所有满足 $gcd(b,n)=1$ 的正整数 $b$ 都有 $b^{n-1}\equiv 1\pmod n$ 成立，则称之为卡迈克尔数），因为卡迈克尔数会导致素数测试结果出错。
通过代码：
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051 ...
整数分解（因数分解）
给出一个正整数，将其写成几个素数的成就，这个过程就叫整数分解，也叫因数分解。
例如：$15=3\times5$，$8=2\times 2\times 2$，$20=2\times 2\times 5$。
下面介绍三种整数分解的方法：
1. 应用试除法对正整数 n 进行分解2. 筛选法对整数分解3. Pollard rho 整数分解方法
1. 应用试除法对正整数 n 进行分解令 $m=n$，从 $2$ ~ $n$一一枚举，如果当前数能够整除 $m$，那么当前数就是 $n$ 的素数因子，并用整数 $m$ 将当前数除尽为止。
若循环结束后 $m$ 是大于 $1$ 的 整数，那么此时 $m$ 也是 $n$ 的素数因子。代码：
1234567891011121314const int N = 100005;int factor[N], cnt; // 素因子和素因子的数目，下标从 1 开始void divide(int n){ cnt = 0; for (int i = 2; i * i <= n; ++i) // i <= sqrt(double(n)) ...
Maximum GCD（最大公约数）
传送门：UVA 11827 - Maximum GCD
题目大意：给你几组数，每组数占输入的一行，但具体几个数没给你，让你算每组数中两两数的最大公约数最大是多少。
解题思路：本来是是打算弄个素数筛，如果两数中有一个数是素数，就不算他俩的最大公约数了，伪暴力枚举两两数的最大公约数比较下。然后突然发现数据范围超级小啊，就直接暴力过了。。。注意下这题还是有几个坑的，首先是得按行读入，再把每行里的数分离出来，这样的话，读第一个数（就是那个测试用例数目）的时候，末尾换行符要处理一下。这里求公约数用的是欧几里得算法。
通过代码：123456789101112131415161718192021222324252627#include <iostream>#include <algorithm>#include <cstdio>#include <sstream>using namespace std;int gcd(int a, int b){ return b == 0 ? a : gcd(b, a % b);}int n ...
算术基本定理
算术基本定理的内容
我们知道任何一个大于 $1$ 的正整数 $n$ 都可以表示成素数之积，即 $n=p_1p_2\cdots p_m$，其中 $p_i(1\leqslant i\leqslant m)$ 是素数。下面就是算数基本定理的一个重要结果，它说明了任何一个大于 $1$ 正整数，都可以由一系列素数相乘得来。
每个大于 $1$ 的正整数 $n$ 都可以被唯一地写成素数的乘积，在乘积中的素因子按照非降序排列。正整数 $n$ 的分解式 $n=p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$ 称为 $n$ 的标准分解式，其中 $p_1,p_2,\cdots,p_k$ 是素数，$p_1\lt p_2\lt \cdots\lt p_k$，且 $\alpha_1,\alpha_2,\cdots,\alpha_k$ 是正整数。
一些性质：(1) 若 $n$ 的标准素因子分解表达式为 $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$，设 $d(n)$ 为 $n$ 的正因子的个数 ...
欧拉函数
其实我原来是把欧拉函数和欧拉定理写在一篇博客里的，但是后来发现欧拉函数特别常用，然后总去那里找也不方便，于是就把它单独分出来了。
欧拉函数 $\varphi(n)$：对于正整数 $n$，欧拉函数是不大于 $n$ 的正整数中与 $n$ 互质的数的数目。
通式：$\varphi(n)=x\prod_{i=1}^n\left(1-\frac{1}{p_i}\right)$，其中 $p_1,p_2,\cdots,p_n$ 为 $x$ 的所有质因子，$x$ 是不为 $0$ 的整数，$\varphi(1)=1$。注意：只取不同的质因数。例如 $12=2\times 2\times 3$，那么 $\varphi(12)=12\times (1-\frac{1}{2})\times (1-\frac{1}{3})=4$。
欧拉函数的一些性质：若 $n=p^k$，$p$ 为质数，$\varphi(n)=p^k-p^{k-1}=(p-1)p^{k-1}$；若 $m,n$ 互质，$\varphi(mn)=\varphi(m)\varphi(n)$；若 $n$ 为奇数，$\varphi(2n)=\varphi ...
Farey Sequence（欧拉函数+前缀和）
传送门：POJ 2478 - Farey Sequence
题目大意：给你一个数 $n$，让你求一个特定序列 $Fn$ 中的元素有多少个。这个序列是这样的，有很多个分数，分子小于分母，分母不大于 $n$，且分子分母的最大公约数为 $1$，这些分数从小到大排列（其实排列这个条件没鸟用）。例如：$F2 = \{\frac{1}{2}\} \\F3 = \{\frac{1}{3},\ \frac{1}{2},\ \frac{2}{3}\} \\F4 = \{\frac{1}{4},\ \frac{1}{3},\ \frac{1}{2},\ \frac{2}{3},\ \frac{3}{4}\} \\F5 = \{\frac{1}{5},\ \frac{1}{4},\ \frac{1}{3},\ \frac{2}{5},\ \frac{1}{2},\ \frac{3}{5},\ \frac{2}{3},\ \frac{3}{4},\ \frac{4}{5}\}$
解题思路：我们可以把问题转化为求对于 $i$ ($i\in [2,n]$)，在不大于 $i$ 的正整数中与 $i$ 互素的数的个数， ...