题意：对于任何正整数 $x$，其约数的个数记作 $g(x)$。例如 $g(1)=1,g(6)=4$。如果某个正整数 $x$ 满足：$g(x)>g(i),0<i<x$，则称 $x$ 为反质数。例如，整数 $1,2,4,6$ 等都是反质数。现在给定一个数 $N$，你能求出不超过 $N$ 的最大的反质数么？

引理 $1$：

题意：给定整数 $N(1\leq N\leq 10^6)$，把 $N!$ 分解质因数。

如果将 $1\sim N$ 分别分解质因数在合并，很明显不可行。

显然，$N!$ 的每个质因子都在 $N$ 之内，我们可以先把 $N$ 之内的质数先筛出来，就完成一半了。

然后就是难点求质数的幂了，设每个质数为 $p$，考虑 $N!$ 内包含多少 $p$。

题意：给定两个整数 $L,R$，$1\leq L \leq R\leq 2^{31},R-L\leq 10^6$，求闭区间 $[L,R]$ 中相邻两个质数的差最大和最小是多少，输出这两个质数。

由题意可知，$L,R$ 的范围过大，肯定不能直接生成 $[1,R]$ 之间的所有质数。

但是 $R-L$ 的范围很小，我们可以直接筛出 $2\sim R$ 之间的所有质数，并把 $L\sim R$ 之间能被这些质数整除的数标记，最后只要看所有没被标记的数，相邻质数两两比较，找出差值最大即可。

题意：给定 $n$，求 $\sum_{i=1}^{n} \gcd(i,n)$，$1<n<2^{31}$。

很明显，暴力求法绝对会 TLE。

我们需要把式子转换一下，设 $\gcd(i,n)=p$，很明显 $p|n$；

我们把两边同时除以 $p$，得到：

即求与 $n/p$ 互质的数的个数，即 $\varphi(n/p)$。

题意：石头游戏在一个 $n$ 行 $m$ 列 $(1≤n,m≤8)$ 的网格上进行，每个格子对应一种操作序列，操作序列至多有 $10$ 种，分别用 $0\sim 9$ 这 $10$ 个数字指明。操作序列是一个长度不超过 $6$ 且循环执行、每秒执行一个字符的字符串。每秒钟，所有格子同时执行各自操作序列里的下一个字符。

问题：求 $\sum_{i=1}^N \lfloor \frac{N}{i}\rfloor,N\leq10^{14}$。

怎么办呢？

暴力？

肯定会 TLE。

这个时候就要请出我们的整除分块了，时间复杂度为 $O \sqrt{N}$。

很明显，在 C++ 语言中，除法都是向下取整的，所以在一段整数区间内，除以同一个数得出来的结果将会成一段一段表示。

A. Tokitsukaze and Enhancement

**题意：**Tokitsukaze的HP值有 $4$ 种类别：

1. HP$\ =(4n+1)$，即HP值除以 $4$,余 $1$，为 $A$ 类；
2. HP$\ =(4n+2)$，即HP值除以 $4$,余 $2$，为 $C$ 类；
3. HP$\ =(4n+3)$，即HP值除以 $4$,余 $3$，为 $B$ 类；
4. HP$\ =4n$，即HP值除以 $4$,余 $0$，为 $D$ 类。

这次来聊一聊DP中的子集型DP。

一.概述

DP，即动态规划。最优化问题是信息学竞赛的一大类题目， 动态规划是解决这类问题的有力武器， 但很多人在尝试理解并运用它时遇到极大的困难！当你学习了足够多的动态规划例题的时候，你会觉得它跟变魔术一样。

二.实质

动态规划实质就是记忆化搜索，是一种高效地实现回溯算法的方法，它的核心是用一个状态记忆表来记住所有中间状态的结果。因此我们要运用动态规划，首先需要发现朴素的回溯算法递归地一而再、再而三地计算一些相同的子问题，接下来需要把答案放在记忆表中而不重复计算。动态规划可以采用记忆化搜索，但记忆化搜索有其缺点，比如要用递归，不能优化空间。所以填表法作为动态规划实现的一种优化方法而广泛使用。

线段树 $(\text{Segment Tree})$ ，是一种二叉搜索树。它将一段区间划分为若干单位区间，每一个节点都储存着一个区间。它功能强大，支持区间求和，区间最大值，区间修改，单点修改等操作。

线段树的思想和分治思想很相像。

线段树的每一个节点都储存着一段区间 $[L…R]$ 的信息，其中叶子节点 $L=R$ 。它的大致思想是：将一段大区间平均地划分成 $2$ 个小区间，每一个小区间都再平均分成 $2$ 个更小区间……以此类推，直到每一个区间的 $L$ 等于 $R$ (这样这个区间仅包含一个节点的信息，无法被划分)。通过对这些区间进行修改、查询，来实现对大区间的修改、查询。

如果最后一头奶牛前面有 $A_n$ 头牛比它高，那么显然他的身高 $H_n=A_n+1$，

如果倒数第二头前面有 $A_{n-1}$ 头牛比它高，那么：

1.如果 $A_{n-1}<A_n$，那么它的身高为 $H_{n-1}=A_{n-1}+1$；

2.如果 $A_{n-1}\geqslant A_n$，那么它的身高为 $H_{n-1}=A_{n-1}+2$.