推歌：SPOTLIGHT HUNTER
麥曉雯聯(lián)動(dòng)出了，沒抽到。我爸把我 75 研究卷霍霍露娜上了導(dǎo)致我沒法免費(fèi)保底。詆毀他。

洛谷傳送

說回正題。設(shè) \(a\) 有 \(n\) 位，所求的 \(a\) 在 \(2^k\) 中距離末位的位數(shù)為 \(m\)，顯然 \(k\ge n+m\)。

發(fā)現(xiàn)很難求出 \(m\)，所以直接枚舉，由于最多只有 \(100\) 位所以是可以接受的。

然后開始把它當(dāng) MO 題解。我們發(fā)現(xiàn)答案需要滿足 \(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\)。我們發(fā)現(xiàn) \(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}}\)，此時(shí)根據(jù)數(shù)學(xué)知識我們有 \(2\) 是 \(5^m\) 的原根，于是就可以構(gòu)造 \(k\)，這道題就結(jié)束了。

真結(jié)束了嗎？顯然是不可能的。如果你直接寫了一個(gè) BSGS 那么復(fù)雜度就爆炸了，所以我們要考慮如何構(gòu)造 \(k\)。

我們發(fā)現(xiàn)這個(gè)問題結(jié)構(gòu)是可以遞推的！于是考慮當(dāng)我們知道了 \(2^x\equiv S\pmod {5^{m}}\) 時(shí)如何求 \(y\) 使得 \(2^y\equiv S\pmod {5^{m+1}}\)。

我們知道當(dāng) \(2^y\equiv S\pmod {5^{m+1}}\) 時(shí)一定有 \(2^y\equiv S\pmod {5^{m}}\)，所以 \(x\equiv y \pmod {\varphi(5^m)}\)，枚舉五個(gè)滿足的就好了。