假设$x$的最高位为$2^{t}$（即$2^{t}le x<2^{t+1}$），并构造出$y=2^{t}xoplus x$，不难发现两者仅在第$t$位上均为1，那么根据异或的性质可得$y=(2^{t}+1)x-2^{t+1}$
由于$x$为奇数，即$(x,2^{t+1})=1$，进而也即$(x,y)=1$
通过扩欧求出一组$ax+by=1$的解，并调整使得$0<ale 2y$且$aequiv 1(mod 2)$，对应的$-2xle b<0$，根据奇偶性可得$ax$为奇数（且$by$为偶数），那么$ax+by=1$即等价于$axoplus (-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 ",(int)ans.size()); 43 for(int i=0;i<ans.size();i++) 44 if (ans[i].p)printf("%lld + %lld ",ans[i].x,ans[i].y); 45 else printf("%lld ^ %lld ",ans[i].x,ans[i].y); 46 return 0; 47 }