例题
简要题意：下边界有 $n$ 个给定点，上边界有 $m$ 个给定点，可以从任意一个点发出一条激光，激光碰到边界会反射，激光到达边界必须打到整数点，问最多可以打到几个给定点
$n,m\le 10^5$
简要题解：能够发现当固定起始点之后只需要确定间距 $T$
注意到当 $T$ 含有大于 $1$ 的质因子的时候将其除掉之后一定能有更多的反射点
所以我们只需要枚举间距点为 $2$ 的幂即可
时间复杂度 $O(n\log^2 n)$
简要题意：给定整数 $x,a,b,p$，求有多少正整数 $n$，满足 $na^n\equiv b(\bmod p)$
$2\le p\le 10^6+3,1\le a,b<p,1\le x\le10^{12}$，保证 $p$ 是素数
简要题解：$na^n\equiv b(\bmod p)$，对于 $a^n$ 我们知道循环节肯定是 $\varphi(p)$，这里保证 $p$ 是素数，有 $\varphi(p)=p-1$
对于 $n$，它的循环节显然是 $p$，那么我们知道 $na^n$ 的循环节就是 $p(p-1)$是，所以我们只需要求 $p(p-1)$ 内有多少合法的 $n$ 即可
我们令 $n=k(p-1)+r,k\in[0,p-1],r\in[0,p-1]$
那么 $na^n\equiv b(\bmod p)$ 可以得到 $k\equiv r-ba^{-r}(\bmod p)$，我们枚举 $r$，可以得到给定范围的 $k$，进而得到 $n$
简要题意：现在有 $q$ 个询问，每次询问区间 $[l,r]$ 内有多少个满足条件的 $x=a^p(a>0,p>1)$
$q\le 10^5,1\le l\le r\le 10^{18}$
简要题解：首先将区间询问转换成前缀差分，然后我们发现对于 $p\ge 3$ 数会很少，大概是 $O(10^6)$，这个东西可以直接预处理，而对于 $p=2$ 的数，直接就等于 $\lfloor\sqrt n\rfloor$，注意 $cmath$ 自带的 $sqrt$ 精度不太行，可以手写一个二分来开根或者使用 $sqrtl$
简要题意：现在有一个 $n\times m$ 的网格图，以及一个以 $(r_b,c_b)$ 为起点的机器人，机器人每一秒会走一步，其坐标的增量为 $(dr,dc)$，初始时 $dr=dc=1$，每当机器人撞到横向或者竖向的墙壁后，$dr$ 或者 $dc$ 会变成 $-1$，机器人在每个位置都有 $p$ 的概率探测与其在横坐标或者纵坐标相同的所有点，当机器人探测到目标点 $(r_d,c_d)$ 后结束，求期望时间
$n\times m\le 10^5$
简要题解：容易得到机器人的行动是有规律的，以 $lcm(n-1,m-1)$ 为一个循环，那么我们首先计算一个循环内期望，令其为 $tans$，同时一个循环内有 $k$ 次可能探测到目标点，第 $i$ 次的时间为 $t_i$，那么 $tans=\sum_{i=0}^{k-1}(1-p)^ipt_i=p\sum_{i=0}^{k-1}(1-p)^it_i$
注意到第 $L$ 次循环的期望为 $(1-p)^{k(L-1)}\sum_{i=0}^{k-1}(1-p)^ip(t_i+(L-1)lcm)$
化简一下得到 $(1-p)^{k(L-1)}(tans+(L-1)lcm\times p\sum_{i=0}^{k-1}(1-p)^i)$，同时我们令 $q=(1-p)^k$，那么最终答案
注意到我们需要枚举一个循环内的所有可以探测到目标点的时间，所以时间复杂度为 $O(nm)$
简要题意：给定一个长度为 $n$ 的数列 $a_i$，现在 $Alice$ 手上有一个数 $x$，$Bob$ 手上的数是 $x+3$，对于这个数列，每个人都从 $a_1$ 开始到 $a_n$ 按顺序操作，对于当前数 $a_i$，可以选择将手上的数 $x$ 加上 $a_i$，或者将 $x$ 异或上 $a_i$，现在给定一个数 $y$，求 $y$ 是 $Alice$ 操作得到的还是 $Bob$ 操作得到的，题目保证 $y$ 一定是其中一个人操作得到的
$n\le 10^5$
简要题解：注意到加法和异或对于数的奇偶性的影响是相同的，而 $Alice$ 和 $Bob$ 的两个数初始奇偶性就不同，所以我们从奇偶性出发判断就行了