我们通过观察可以发现 $11\cdots1$ 可以变化为 $\frac{10^{n}-1}{9}$,于是根据取模的性质,我们可以把原式两边同乘九再加一,原式变为 $10^{n} \equiv k \cdot 9 + 1 \pmod m$,发现这是个 BSGS 的标准式子,由于 $m$ 保证为质数,所以也不必用拓展 BSGS。
然后愉快地交了一发,发现只有 80 分。再看一眼数据范围——中间过程相乘会爆 long long,所以我们需要快速乘来防止溢出。然而丧心病狂的出题人卡 $log_{n}$ 的快速乘,所以我们需要复杂度更优常数更小的快速乘:
1 | // 传说中复杂度更优的O(1)快速乘 |
看着这么高级其实就是利用了小学生都会的乘法分配律。
我们要计算 $a \cdot b;mod;p$,设 $b=L+R$。
那么原式就变为 $a\cdot(L+R);mod;p=((a\cdot L);mod;p+(a\cdot R);mod;p);mod;p$。
我们把 $L$ 钦定为 $b$ 的二进制前 $x$ 位,$R$ 为 $b$ 的后 $(64-x)$ 位。
就得到了以上的代码(以上这份代码 $x=25$)。
用上这样的快速乘就可以 AC 了。
以下为代码:
1 |
|