ABC414
BrotherCall
·
·
个人记录
B - String Too Long
## C - Palindromic in Both Bases
经典套路构造回文，这样复杂度就是根号的。
注意奇数长度的回文只要砍掉枚举一半的最后一位即可。
## D - Transmission Mission
先考虑 $N = M$，不难发现每个点放个 $0$，答案即为 $0$。
考虑 $M = N - 1$，肯定是找到挨得最近的两个基站，在这两个基站的正中间建一座，代价是两个基站之间的距离。
$M$ 每少 $1$，都是这个操作的不断重复。
所以最后答案就是两两基站距离取前 $N - M$ 小的之和。
## E - Count A%B=C
不难发现答案即 $\displaystyle\frac{n(n+1)}{2} - \sum\limits^n_{i=1}d(i)$，$d(i)$ 为 $i$ 的因子数。
因子数我会的最优的也就是线性筛 $O(n)$，但这题 $n\le 10^{12}$。
考虑枚举因子呢，对于因子 $d$，有 $\displaystyle \frac{n}{d}$ 个数以它为因子。
所以 $\displaystyle\sum\limits^n_{i=1}d(i) = \sum\limits_{i=1}^n\frac{n}{i}$，整除分块即可，复杂度 $O(\sqrt n)$。