首先考虑 $2|a$，发现此时 $a^{64}\equiv 0\pmod{2^{64}}$，检查 $0\sim 64$ 即可。

设 $p$ 为最小正整数使得 $a^p\equiv 1\pmod{2^{64}}$，因为有 $a^{2^{63}}\equiv 1\pmod{2^{64}}$，所以 $p=2^k$。

那么此时的答案只可能在 $[0,2^k)$ 之间。且我们知道 $a^1,a^2,a^4,a^8,...,a^{2^{k-1}}$ 两两不同。

一个观察是 $\operatorname{lowbit}(a^1-1),\operatorname{lowbit}(a^2-1),\operatorname{lowbit}(a^4-1),...$ 是严格递增的。

具体证明很简单：设 $a^{2^k}=c2^d+1$，则 $a^{2^{k+1}}=(c2^d+1)^2=c^22^{2d}+c2^{d+1}+1=2^{d+1}(c^22^{d-1}+c)+1$。

于是就可以按位确定了。对于一个 $k$，只有 $a^1\sim a^{2^k}$ 可以决定从最低位到 $\operatorname{lowbit}(a^{2^k}-1)$ 位的具体值，所以从低到高按位确定即可。