根据扩展欧几里得 ax-by=d 由于需要异或为1，则较小数为偶数。根据d的正负相对应调整ax与by的相对大小。 其余步骤官方题解已经详细论述，在此不赘述，加以链接
#include<bits/stdc++.h> using namespace std; #define pii pair<int,int> #define ll long long #define mp make_pair #define pb push_back #define mt(a,val) memset(a,val,sizeof(a)) const int mod = 1e9 + 7; const int inf = 0x3f3f3f3f; const ll INF = 0x3f3f3f3f3f3f3f3f; const double pi = 3.14159265; const int maxn = 1e5 + 7; ll a, b; ll x, y; int index = 0; long long exgcd(long long a,long long b,long long &x,long long &y)//x,y的类型long long { if(b==0)//如果b为零则ax=c，c为最大公约数=a，则 x=1 { x=1; y=0; return a; } long long d=exgcd(b,a%b,x,y); int t=x;//ax1+by1=ay2+b(x2-a/b*y2) x=y; y=t-a/b*y;//右边的y是ecgcd得出的y //另x>0 x,y的通解x=x0+b/d*t;y=y0-a/d*t t为任意常数 return d;//x，y均可能为负 d为最大公约数 } vector <pair <ll, ll> > ans; vector <int> op; ll work(ll x, ll a) { ll res = x; ll an = 0; while(a) { if(a & 1) { if(an) { ans.pb(mp(an, res) ); op.pb(0); } an += res; } ans.pb(mp(res, res)); op.pb(0); res *= 2; a >>= 1; } return an; } int main() { scanf("%lld", &x); for(int i = 60; i >= 0; i --) { if(x & (1ll << i)) { index = i; break; } } ll tem = x; for(int i = 0; i < index; i ++) { ans.pb(mp(tem, tem)); op.pb(0);//+ tem *= 2; } y = tem ^ x; ans.pb(mp(tem, x)); op.pb(1); //^ int gcd = exgcd(x, -y, a, b); while(((b * y) & 1 ) == 0 && gcd == -1) { b += x; a += y; } while(((b * y) & 1 ) == 1 && gcd == 1) { b += x; a += y; } work(x, a); work(y, b); printf("%d\n", ans.size() + 1); for(int i = 0; i < ans.size(); i ++) { printf("%lld ", ans[i].first); printf("%c ", op[i] ? '^' : '+'); printf("%lld\n", ans[i].second); } printf("%lld ^ %lld\n", x * a, y * b); //printf("%lld\n", (x * a) ^ (y * b) ); } ```**加粗样式**