前置知识

1. 对素数 $p$，若 $n=p^k m$，其中 $p\nmid m$，则定义 $\nu_p(n)=k$，表示 $n$ 的分解中 $p$ 的指数
2. 对素数 $p$，$x \equiv y \pmod{p^r} \iff p^r\mid x-y \iff \nu_p(x-y)\ge r$
3. (LTE) 若 $n$ 是正偶数，$x, y$ 是奇数，$\nu_{2}(x^n - y^n) = \nu_{2}(x - y) + \nu_{2}(x + y) + \nu_{2}(n) - 1$

思路

下设 $A$ 是奇数。

如果考察 $(2 A_{1} + 1)^{n}$ 或 $(\sum 2^{i} A_{i})^{n}$，会产生大量二项式系数，没有很好的性质。

考虑从 $n$ 入手，将 $n$ 二进制分解，考察每个 $A^{2^{k}}$ 对答案的影响，其中 $k \geqslant 1$。

先看 $A^{2^{k}} \equiv 1 \pmod {2^{r}}$，这是说乘上 $A^{2^{k}}$ 对答案的低 $r$ 位没有影响。条件等价于 $\nu_{2}(A^{2^{k}} - 1) \geqslant r$，记 $$f_{k} = \nu_{2}(A^{2^{k}} - 1) = \nu_2(A-1)+\nu_2(A+1)+k-1$$

$f_{k}$ 递增，因此 $n$ 中比 $k$ 高的二进制位，无法再改变 $A^{n}$ 中的低 $f_{k}$ 位。在确定 $n$ 的第 $k$ 位时，就需要保证 $A^{n}$ 的低 $f_{k+1}$ 位与 $B$ 相同。

算法

从低到高位枚举，对于第 $k$ 位，如果当前 $A^{n} \not\equiv B\pmod{2^{f_{k+1}}}$，更新 $n\leftarrow n+2^k$。