ABC414

B - String Too Long

\sum l

会爆 ll，这个阴点排除了即可。

经典套路构造回文，这样复杂度就是根号的。

注意奇数长度的回文只要砍掉枚举一半的最后一位即可。

先考虑

N = M

，不难发现每个点放个

0

，答案即为

0

。

考虑

M = N - 1

，肯定是找到挨得最近的两个基站，在这两个基站的正中间建一座，代价是两个基站之间的距离。

M

每少

1

，都是这个操作的不断重复。

所以最后答案就是两两基站距离取前

N - M

小的之和。

不难发现答案即

\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)

。