CF1427E Xum

https://www.luogu.com.cn/problem/CF1427E

首先设 y = x < < t y=x< 然后令 z = x ⊕ y z=x oplus y z=x⊕y, 再令 o = z + y o=z+y o=z+y
然后令 o ⊕ ( y < < 1 ) ⊕ x ooplus(y<<1)oplus x o⊕(y<<1)⊕x就可以得到 y y y的第二低位
然后一路往上把 y y y消得只剩下最低位，即 x x x的最高位

然后把 x x x的最高位消掉即可

一路消下去就是答案

code:

#include
#define ll long long
using namespace std;
struct A {
    ll x, y, o;
};
vector ans;
ll calc(ll x) {
    ll y = x, sy = x >> 1;
    while(sy) {
        ans.push_back((A){y, y, 0});
        sy >>= 1; y <<= 1;
    }
    ans.push_back((A){x, y, 1});
    ll z = x ^ y;
    ans.push_back((A){z, y, 0});
    ll o = y + z;
    ans.push_back((A){y, y, 0});
    ll yy = y + y;
    ans.push_back((A){o, x, 1});
    ll yq = o ^ x;
    ans.push_back((A){yy, yq, 1});
    ll b = yy ^ yq;
    while(y != (y & -y)) {
        if(y & b) {
            ans.push_back((A){y, b, 1});
            y ^= b;
        }
        ans.push_back((A){b, b, 0});
        b = b + b;
    }
    ans.push_back((A){x, y, 1});
    return x ^ y;
}
ll n;
int main() {
    scanf("%lld", &n);
    while(n != 1) n = calc(n);
    printf("%dn", ans.size());
    for(int i = 0; i < ans.size(); i ++) {
        if(ans[i].o == 0) printf("%lld + %lldn", ans[i].x, ans[i].y);
        else printf("%lld ^ %lldn", ans[i].x, ans[i].y);
    }
    return 0;
}