什么是P问题、NP问题和NPC问题

被浏览

为了准备初赛,发现自己对P问题、NP问题和NPC问题一点都不熟悉,在网上找到了 Matrix67 大佬的博文,感觉很棒,所以转载一下。

其实是太久没写博文了来充数的

原文链接

遵循署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

以下为原文,对公式略加修改,删改了逻辑电路部分内容,并且重绘了逻辑电路图(原文排版实在难以看清)。

洛谷P4884 - 多少个1?

 题解 / 洛谷
被浏览

我们通过观察可以发现 $11\cdots1$ 可以变化为 $\frac{10^{n}-1}{9}$,于是根据取模的性质,我们可以把原式两边同乘九再加一、原式变为 $10^{n} \equiv k \cdot 9 + 1 \pmod m$,发现这是个 BSGS 的标准式子,由于$m$保证为质数,所以也不必用拓展 BSGS。