假设$x$的最高位为$2^{t}$（即$2^{t}\le x<2^{t+1}$），并构造出$y=2^{t}x\oplus x$，不难发现两者仅在第$t$位上均为1，那么根据异或的性质可得$y=(2^{t}+1)x-2^{t+1}$

由于$x$为奇数，即$(x,2^{t+1})=1$，进而也即$(x,y)=1$

通过扩欧求出一组$ax+by=1$的解，并调整使得$0<a\le 2y$且$a\equiv 1(mod\ 2)$，对应的$-2x\le b<0$，根据奇偶性可得$ax$为奇数（且$by$为偶数），那么$ax+by=1$即等价于$ax\oplus (-b)y=1$，由此计算可得

另外，计算过程中需要实现乘法，这借助类似快速幂的做法实现即可

最终操作次数（和时间复杂度）约为$o(\log n)$，数字范围约为$2n^{3}$，可以通过

1 #include
2 using namespace std;
3 #define ll long long
4 struct Data{
5 int p;
6 ll x,y;
7 };
8 vectorans;
9 ll n,m,x,y;
10 void calc(ll n,ll m){
11 m--;
12 ll s=n,sum=n;
13 while (m){
14 if (m&1){
15 ans.push_back(Data{1,s,sum});
16 sum+=s;
17 }
18 ans.push_back(Data{1,s,s});
19 s<<=1,m>>=1;
20 }
21 }
22 void exgcd(ll a,ll b,ll &x,ll &y){
23 if (!b){
24 x=1,y=0;
25 return;
26 }
27 exgcd(b,a%b,y,x);
28 y-=(a/b)*x;
29 }
30 int main(){
31 scanf("%lld",&n);
32 ll t=2;
33 while ((t<<1)<=n)t<<=1;
34 calc(n,t);
35 m=((n*t)^n),ans.push_back(Data{0,n*t,n});
36 exgcd(n,m,x,y);
37 x=(x%m+m)%m;
38 if (x%2==0)x+=m;
39 y=(n*x-1)/m;
40 calc(n,x),calc(m,y);
41 ans.push_back(Data{0,n*x,m*y});
42 printf("%d\n",(int)ans.size());
43 for(int i=0;i<ans.size();i++)
44 if (ans[i].p)printf("%lld + %lld\n",ans[i].x,ans[i].y);
45 else printf("%lld ^ %lld\n",ans[i].x,ans[i].y);
46 return 0;
47 }