题意
做法一
以下均在二进制意义下进行
定义1：令(x^1)为(x)去掉最高位的数，(x_1)为(x)去掉最低的(1)及后面一截的数
如(1101100^1=101100)，(1101100_1=1101)
定义2：令((x,y))为数(x,y)拼接后形成的数
定义3：令(|x|)为数(x)的位数
令给出的数为(x)，考虑每次去掉最高位为(1)的，即生成(2^{|x|})
((x,0 imes |x|-1))：
((x_1,0,x^1))：((x,0 imes |x|-1)oplus x)
((x_1<<1,x))：((x_1,0,x^1)+(x,0 imes |x|-1))
((x_1<<1,0 imes |x|))：((x_1<<1,x)oplus x)
((x,0 imes |x|))：((x,0 imes |x|-1)<<1)
(2^{|x|+1})：((x_1<<1,0 imes |x|)oplus(x,0 imes |x|))
利用(2^{|x|+1})将((x,0 imes |x|-1))的一些高位取掉，只留下(2^|x|)
做法二
令(x)为初始给出的奇数，显然通过(O(logn))次可以表示出(nx)
令(e)为最大的(2^e<x)
结论1：((x,(2^ex)oplus x)=1)
证明：
(2^ex=2^ex+x-2^{e+1})
结论2：存在(a,bge 0)，(ax-by=1)其中(b)为偶数
证明：
根据裴蜀定理一定存在(a,bge 0)，(ax-by=1)
若(b)为奇数，则将(b)加上(x)，(a)加上(y)
由于(ax,byge 0,2|by)，(ax-by=1)，所以(axoplus by=1)