Xum

1427E - Xum
We present two different solutions. The first solution is by Anton, the second is mine.

The first solution is deterministic, it is fundamentally based on Bezout's Theorem and comes with a proof. It performs ≈100 operations and writes numbers up to O(x3).
The second solution is randomized, uses some xor-linear-algebra and comes without a proof. It performs ≈1000 operations and writes numbers up to O(x2).
There are many variations on the randomized solution, some of them being quite messy. The randomized solution we present is rather clean. Let us remark that, due to the constraint x≤999,999, it is possible to test on your personal computer whether a certain algorithm is correct or not on all possible inputs.
Deterministic, provable, "gcd" solution

Step 0: If u is written on the blackboard, then we can write nu on the blackboard with O(log(n)) operations.

How? Just using the sum operation as in the binary exponentiation (same algorithm, just replace multiplication with addition and exponentiation with multiplication).

Step 1: Write on the blackboard a number y coprime with x.

Let e∈N be the largest integer such that 2e≤x (i.e., 2e is the largest bit of x). Notice that y=(2ex)∧x=(2e+1)x−2e+1 and therefore gcd(x,y)=gcd(x,2e+1)=1.

Step 2: Write 1=gcd(x,y) on the blackboard.

Let a,b≥0 be such that ax−by=1 (a,b exist thanks to Bezout's theorem) with b even (if b is odd, we can add y to a and x to b, getting an even b). Since by is even, we have ax∧by=1 and therefore we are able to write 1 on the blackboard.

Randomized, unproven, linear-algebraic solution

We are going to talk about subspaces and basis; they shall be understood with respect to the operation xor on nonnegative integers.

The rough idea is to sample randomly two numbers from the subspace generated by the numbers currently on the blackboard and write their sum on the blackboard.

First, we choose the maximum number of bits L that any number on the blackboard will ever have. A good choice is 2L>x2 (L=40 works for any odd x below 106).

We iterate the following process until 1 belongs to the subspace generated by the numbers written on the blackboard.

Let S be the subspace generated by the numbers currently on the blackboard (i.e., the set of numbers that can be written as the xor of some numbers on the blackboard). Let b1,…,bk be a basis for S. Randomly choosing k bits e1,…,ek we can produce a random element in S as
(e1b1)∧(e2b2)∧⋯∧(ekbk).
Let us choose two random numbers u,v∈S.

If u+v≥2L, we choose a different pair of numbers.
If u+v∈S (we can check this in O(k) since we know a basis for S), we choose a different pair of numbers.
Otherwise, we add u+v to S and update the basis accordingly.
It turns out that this approach solves all odd values 3≤x≤999,999 instantaneously.

Could we choose a much smaller L? The answer is no. If x=219+1 then there is a xor-subspace S that contains x and such that if u,v∈S and u+v<238 then u+v∈S. Notice that this implies that any strategy needs to write on the blackboard some "some big numbers". This is why any approach that avoids large numbers by design is doomed to fail.

Comment: Why should this solution work? Fundamentally, and this is the main idea of the problem, because the two operations + and ∧ are not related by any strange hidden structure. It would be a miracle if we could find a very big subspace for ∧ that is closed also for +. And, since miracles are rare, here there is no miracle.

It should not be very hard to show that this solution works for any odd x, i.e. there is not a subspace that contains x and is closed for sums that are below 2L (if 2L>x2). Nonetheless, I could not show it. On the other hand, I think that proving that this solution has a very good (expected) time-complexity is very hard, but I would be happy if someone proves me wrong.


LL Inverse(LL n, LL m) {
    n %= m;
    if (n <= 1) return n; // Handles properly (n = 0, m = 1).
    return m - ((m * Inverse(m, n) - 1) / n);
}


vector<ULL> A;
vector<char> op;
vector<ULL> B;

void add_op(ULL a, char o, ULL b) {
    if (a == 0 or b == 0) return;
    A.push_back(a);
    op.push_back(o);
    B.push_back(b);
}

ULL xxor(ULL a, ULL b) {
    add_op(a, '^', b);
    return a^b;
}

ULL sum(ULL a, ULL b) {
    add_op(a, '+', b);
    return a+b;
}

ULL mul(ULL a, ULL n) {
    ULL pot = a;
    ULL curr = 0;
    while (n > 0) {
        if (n%2) curr = sum(curr, pot);
        pot = sum(pot, pot);
        n /= 2;
    }
    return curr;
}

int main() {
    ULL x;
    cin >> x;
    while (x != 1) {
        for (ULL n = 2; ; n *= 2) {
            sum((n/2)*x, (n/2)*x);
            if (((n*x)^x)%x == 0) continue;
            ULL y = xxor(n*x, x);
            ULL g = __gcd(x, y);
            ULL a = mul(x, Inverse(x/g, y/g));
            ULL b = mul(y, (a-g)/y);
            ULL pot = 1<<20; // must be larger than g
            ULL q = (pot- b%pot) * Inverse(x, pot) % pot;
            ULL c = mul(x, q);
            x = xxor(sum(a, c), sum(b, c));
            break;
        }
    }

    cout << A.size() << "\n";
    for (int i = 0; i < (int)A.size(); i++)
        cout << A[i] << " " << op[i] << " " << B[i] << "\n";
}

#include<bits/stdc++.h>

int main() {
    using namespace std;
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int64_t X; cin >> X;

    struct op_t {
        int64_t a, b;
        char v;
    };
    vector<op_t> ops; ops.reserve(1e5);

    while (X > 1) {
        int L = (63 - __builtin_clzll(X));
        assert(X & (1ll << L));
        for (int i = 0; i < L; i++) {
            ops.push_back({X << i, X << i, '+'});
        }
        int64_t a = X << L;
        ops.push_back({a, X, '^'});
        int64_t b = a ^ X;

        for (int i = 0; i <= L; i++) {
            if (b & (1ll << i)) {
                ops.push_back({a, (X << i), '+'});
                ops.push_back({b, (X << i), '+'});
                a += (X << i);
                b += (X << i);
            }
            assert(!(b & (1ll << i)));
        }
        ops.push_back({a, b, '^'});
        int64_t nx = a ^ b;
        assert(nx != 0);
        assert(__builtin_clzll(nx) >= __builtin_clzll(X));
        X = nx;
    }

    cout << ops.size() << '\n';
    for (auto op : ops) {
        cout << op.a << ' ' << op.v << ' ' << op.b << '\n';
    }

    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <ctime>

#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;
typedef pair<ll, char> pic;
typedef pair<pic, ll> pici;

const ll INFL=1000000000000000007;

ll x;
vector<ll> basis;
vector<pii> st;

vector<pici> ans;

ll trybasis(ll x)
{
    ll i;
    st.clear();

    for(i=basis.size()-1;i>=0;i--)
        if((x^basis[i])<x){
            st.pb({x, basis[i]});
            x^=basis[i];
        }
    return x;
}

int main()
{
    ios_base:: sync_with_stdio(0); cin.tie(0); cout.tie(0);

    ll i;

    srand(time(NULL));

    cin >> x;
    basis.pb(x);

    while(basis[0]!=1){
        ll a=basis[rand()%basis.size()], b=basis[rand()%basis.size()];
        if(a+b>INFL)
            continue;
        ll f=trybasis(a+b);
        if(f!=0){
            basis.pb(f);
            sort(basis.begin(), basis.end());
            ans.pb({{a, '+'}, b});
            for(i=0;i<st.size();i++)
                ans.pb({{st[i].first, '^'}, st[i].second});
        }
    }

    cout << ans.size() << endl;
    for(i=0;i<ans.size();i++)
        cout << ans[i].first.first << " " << ans[i].first.second << " " << ans[i].second << endl;

    return 0;
}