CF913G Power Substring
推歌：SPOTLIGHT HUNTER麦晓雯联动出了，没抽到。我爸把我 75 研究卷霍霍露娜上了导致我没法免费保底。诋毁他。
洛谷传送
说回正题。设 \(a\) 有 \(n\) 位，所求的 \(a\) 在 \(2^k\) 中距离末位的位数为 \(m\)，显然 \(k\ge n+m\)。
发现很难求出 \(m\)，所以直接枚举，由于最多只有 \(100\) 位所以是可以接受的。
然后开始把它当 MO 题解。我们发现答案需要满足 \(2^k\equiv a\times 10^m+b\pmod {10^{n+m}}\)。由于 \(2^{n+m}\mid 2^k\) 且 \(2^{n+m}\mid 10^{n+m}\)，所以 \(2^{n+m}\mid a\times 10^m+b\)。
又显然 \(2^k\) 的末位不能是 \(0\) 或 \(5\)，所以 \(5^{n+m}\nmid a\times 10^m+b\)。
我们可以直接取 \(b= -a\times 10^m \bmod 2^{n+m}\)，如果 \(5\mid b\) 就令 \(b\to b+2^{n+m}\)，这样 \(a\times 10^m+b\) 就符合了。
好的接下来我们思考如何求解 \(k\)。我们发现 \(2^k\equiv a\times 10^m+b\pmod {10^{n+m}}\Rightarrow 2^{k-n-m}\equiv \frac{a\times 10^m+b}{2^{n+m}}\pmod {5^{n+m}}\)，此时根据数学知识我们有 \(2\) 是 \(5^m\) 的原根，于是就可以构造 \(k\)，这道题就结束了。
真结束了吗？显然是不可能的。如果你直接写了一个 BSGS 那么复杂度就爆炸了，所以我们要考虑如何构造 \(k\)。
我们发现这个问题结构是可以递推的！于是考虑当我们知道了 \(2^x\equiv S\pmod {5^{m}}\) 时如何求 \(y\) 使得 \(2^y\equiv S\pmod {5^{m+1}}\)。
我们知道当 \(2^y\equiv S\pmod {5^{m+1}}\) 时一定有 \(2^y\equiv S\pmod {5^{m}}\)，所以 \(x\equiv y \pmod {\varphi(5^m)}\)，枚举五个满足的就好了。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 懂技术并乐意极积无私分享的人越来越少。珍惜 这个好，看起来很实用 收藏一下 不知道什么时候能用到 感谢发布原创作品，程序园因你更精彩 懂技术并乐意极积无私分享的人越来越少。珍惜 用心讨论，共获提升！ 很好很强大我过来先占个楼 待编辑 前排留名，哈哈哈 感谢分享，下载保存了，貌似很强大 感谢分享，学习下。 感谢分享，下载保存了，貌似很强大 感谢分享，下载保存了，貌似很强大 yyds。多谢分享 过来提前占个楼 用心讨论，共获提升！ 谢谢分享，试用一下 谢谢分享，辛苦了 谢谢分享，辛苦了 这个有用。
页:
[1]
2