题解：AT_abc448_e [ABC448E] Simple Division

· · 题解

题目传送门。

首先我们发现 \lfloor \frac{n}{m}\rfloor=\frac{n}{m}-\frac{n\bmod m}{m}，因此考虑求出 \frac{n}{m} 和 \frac{n\bmod m}{m} 对 10007 取模后的结果即可。由于 m\le10000，因此我们只需要使用逆元求出 \frac1m\bmod10007 的值然后乘上两个分母即可。

我们发现，往 a 之后添加 l 个 c 等价于 a\gets 10^l\times a+\underset{l个1}{\underbrace{11\dots1}}\times c。10^l\times a\bmod m 直接用快速幂即可，关键问题就是 \underset{l个1}{\underbrace{11\dots1}}\bmod m 怎么求。我们先令这个东西为 f(l)，利用分治思想，显然，

f(l)=\begin{cases} (10^{\frac{l}{2}}\times f(\frac{l}{2})+f(\frac{l}{2}))\bmod m&2\mid l\\ (10\times f(l-1)+1)\bmod m&2\nmid l \end{cases}

能够知道这样的时间复杂度是 O(\log l) 的。那么就做完了。