这是我的第一篇题解。以后每攒 5 道题会发一篇。除了需要特别注意的部分，尽量避免直接放代码。
坚持下去。
CF 1444 A Division
给定一对数 $p$ 和 $q$，求尽可能大的 $x$，使 $x$ 可整除 $p$，而 $q$ 不能整除 $x$。
$1 \leq p \leq 10^{18}, 2 \leq q \leq 10^{9}$
首先，如果 $q$ 不能整除 $p$，那么答案就是 $p$ 自己。其次，$x$ 一定是 $p$ 去掉若干质因数得到的。
去掉了几种质因数呢？明确一个概念：整除关系代表除数拥有被除数所有种类的质因数，且次数都不大于被除数。那么不可整除就代表除数至少一个质因数是被除数没有的，或者次数大于除数。这里既然只能扣除，那么扣除多种得到不可除的情况，一定能转化成只扣除一种，而转化后得到的答案 $x$ 显然较大。所以我们可以对每一种质因数分别去掉若干个，得到的结果再取最大。
大框架是对 $q$ 的分解质因数，1e9 的数据分解下来还是很小的。对每个质因数，从 $p$ 里扣掉它直到结果满足题设（可能一个都不扣，当 $p$ 没有这个数时，即开头提到的情况），再和上一个结果取最大。这些可以压到分解质因数的循环里去做。
CF 1451 C String Equality
给定两个长度为 $n$ 的小写字符串 $a$ 和 $b$，以及一个整数 $k \leq n$。对 $a$ 有以下两种操作：
- 交换相邻的两个字符
- 选定长为 $k$ 的一个区间，当区间内各字符相等时，将它们都变成字典序下一个字母。对 z 不能如此操作。
对给定的输入，输出是否能通过以上两种操作使两个字符串相等。
$2 \leq n \leq 10^6, 1 \leq k \leq n$
第一个操作代表我们可以把 $a$ 的字符任意组合。原来散开的相等字符都可以排在一起，然后进行变化。从 a 到 z 的变化是不可逆的，那么从 a 开始，对每个 $a$ 和 $b$ 都有的字符，留下和 $b$ 中同样多的，剩下的全部转化到字典序下一个字符。如果这样的操作一直到 z 都可行，则是可以让两个字符串相等的，否则不可以。
转化的条件是先保留和 $b$ 同样多的字符，且每次只能以 $k$ 个为一组，统一转化。
CF 859 C Pie Rules
甲和乙玩取数（拿派）游戏，规则如下：
有一个决定权，初始在乙手上。数列是固定顺序的，对于每个数，拥有决定权的人可以把这个数给一个玩家，同时把决定权给另一个玩家。双方都想让自己拿到的数总值最大。
假设双方都按最优方案，求最终分别拿到的数值总和。
一直要把决定权留给自己的话好吃的派就都是别人的了
一道 dp 题。
既然每个人都会按最优方案选（只要决定权在自己手上），那么只从状态来考虑，在每个位置能行使决定权的人是状态转移的推力。于是考虑用 dp[i] 记录在第 $i$ 个位置拿到决定权的人能获得的最大总值。再看方向，由于在每个位置拿到决定权后，后续取数存在一个确定的最优，那么从后往前 d 是较好的想法。于是 dp[i] 记录在第 $i$ 个位置拿到决定权的人，之后能获得的最大总值。
那么初始状态是 dp[n] = n，目标状态是 dp[1] （根据题设，这是乙的）。接下来考虑状态转移方程。
对每个拿到决定权的人，他之后能拿到的最大值与是否交出决定权相关。若不交出，他能拿到的值和下一个位置相等；交出，则能拿到的值是 当前位置 + 下一个位置开始的后缀和 - 下一个位置，即 当前位置开始的后缀和 - 下一个位置。两者取最大即可。
实际上 dp[i] 记录的是在第 $i$ 位置拿到决定权的人之后能获得的最大。
CCPC 2020 秦皇岛站 G Good Number
给定 $n$ 和 $k$，有 $i \in [1, n]$ 且 $\lfloor \sqrt[k]{i}\rfloor | i$，求 $i$ 的个数。
$1\leq n, k \leq 10^9$
由于是向下取整，考虑按 $[i^k, (i + 1)^k)$ 将 $[1, n]$ 分段，段内开次方向下取整都会得到 $i$，那么段内所有可以被 $i$ 整除的数就是 Good Number。最后一段显然有可能不全。敲一下快速幂就好了。注意考虑超过 long long 的情况。
POJ 3279 FlipTile
$M \times N$ 的黑白棋棋盘，每次翻一个棋子时，与它四连通的棋子也会翻转。给定棋盘尺寸和棋子状态，以棋盘的形式输出全部翻转为白色的方案，每个位置的数代表该位置的翻转次数，要求翻转次数最小且字典序最小。不能完成时输出 “IMPOSSIBLE”。
$1 \leq M, N \leq 15$
搜索题。显然一个位置翻转奇数次等价于翻转一次，偶数次等价于不翻转。按行来考虑，每行的一个位置要被翻转当且仅当它上一行对应位置是黑色，然后枚举第一行的翻转状态即可。注意搜到了一个方案不能停，要比较总翻转次数和字典序，保留当前最符合题设的答案。
当时被这道题卡了挺久，主要在记录当前最优和第一个枚举状态这些小地方，一度想要放弃 kuangbin 的题集（一遇到 POJ 的题就难受，各种 WA）。所幸撑住了。继续。