假设$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<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 struct Data{
 5     int p;
 6     ll x,y;
 7 };
 8 vector<Data>ans;
 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 }

View Code