How many operations will have $$$x = 0$$$.

Try $$$k = 2$$$.

If $$$k$$$ is 1, we can only subtract 1 in each operation, and our answer will be $$$n$$$.

Now, first, it can be seen that we have to apply at least $$$n$$$ mod $$$k$$$ operations of subtracting $$$k^0$$$ (as all the other operations will not change the value of $$$n$$$ mod $$$k$$$). Now, once $$$n$$$ is divisible by $$$k$$$, solving the problem for $$$n$$$ is equivalent to solving the problem for $$$\frac{n}{k}$$$ as subtracting $$$k^0$$$ will be useless because if we apply the $$$k^0$$$ subtraction operation, then $$$n$$$ mod $$$k$$$ becomes $$$k-1$$$, and we have to apply $$$k-1$$$ more operations to make $$$n$$$ divisible by $$$k$$$ (as the final result, i.e., 0 is divisible by $$$k$$$). Instead of doing these $$$k$$$ operations of subtracting $$$k^0$$$, a single operation subtracting $$$k^1$$$ will do the job.

So, our final answer becomes the sum of the digits of $$$n$$$ in base $$$k$$$.

The complexity of the solution is $$$O(\log_{k}{n})$$$ per testcase.

#include <bits/stdc++.h>
using namespace std;
 
int find_min_oper(int n, int k){
	if(k == 1) return n;
	int ans = 0;
	while(n){
		ans += n%k;
		n /= k;
	}
	return ans;
}
 
int main()
{
	int t;
	cin >> t;
	while(t--){
		int n,k;
		cin >> n >> k;
		cout << find_min_oper(n,k) << "\n";
	}
    return 0;
}

The final state of $$$i$$$th bulb (on or off) is independent of $$$n$$$.

The final state of the $$$i$$$th bulb tells us about the parity of number of divisors of $$$i$$$.

For any bulb $$$i$$$, its final state depends on the parity of the number of divisors of $$$i$$$. If $$$i$$$ has an even number of divisors, then bulb $$$i$$$ will be on; else it will be off. This translates to, if $$$i$$$ is not a perfect square, bulb $$$i$$$ will be on; else it will be off. So now the problem is to find the $$$k$$$th number which is not a perfect square. This can be done by binary searching the value of $$$n$$$ such that $$$n- \lfloor \sqrt{n} \rfloor = k$$$ or the direct formula $$$n$$$ = $$$\lfloor k + \sqrt{k} + 0.5 \rfloor$$$.

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin >> t;
    while(t--){
        long long k, l = 1, r = 2e18;
        cin >> k;
        while(r-l > 1){
            long long mid = (l+r)>>1;
            long long n = mid - int(sqrtl(mid));
            if(n >= k) r = mid;
            else l = mid;
        }
        cout << r << "\n";
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin >> t;
    while(t--){
        long long k;
        cin >> k;
        cout << k + int(sqrtl(k) + 0.5) << "\n";
    }
    return 0;
}

Try to find some independent operations/combinations.

The expression is independent for each digit in binary representation

The first observation is that the expression $$$a|b - a&c = d$$$ is bitwise independent. That is, the combination of a tuple of bits of $$$a, b, and\ c$$$ corresponding to the same power of 2 will only affect the bit value of $$$d$$$ at that power of 2 only.

This is because: \begin{enumerate} \item We are performing subtraction, so extra carry won't be generated to the next power of 2. \item Any tuple of bits of $$$a, b, and\ c$$$ corresponding to the same power of 2 won't result in -1 for that power of 2. As that would require $$$a|b$$$ to be zero and $$$a&c$$$ to be one. The former condition requires the bit of $$$a$$$ to be zero, while the latter requires it to be one, which is contradicting. \end{enumerate}

Now, let us consider all 8 cases of bits of a, b, c and the corresponding bit value of d in the following table:

\begin{center} \begin{tabular}{|c c c |c|} \hline b & c & a & d \ \hline 0 & 0 & 0 & 0 \ 0 & 0 & 1 & 1 \ 0 & 1 & 0 & 0 \ 0 & 1 & 1 & 0 \ 1 & 0 & 0 & 1 \ 1 & 0 & 1 & 1 \ 1 & 1 & 0 & 1 \ 1 & 1 & 1 & 0 \ \hline \end{tabular} \end{center}

So, clearly, for different bits of $$$b, c,$$$ and $$$d$$$, we can find the value of the corresponding bit in $$$a$$$, provided it is not the case when bit values of $$$b, c,$$$ and $$$d$$$ are 1,0,0 or 0,1,1, which are not possible; so, in that case, the answer is -1.

#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
void solve() {
    ll a = 0, b, c, d, pos = 1, bit_b, bit_c, bit_d, mask = 1;
    cin >> b >> c >> d;
    for (ll i = 0; i < 62; i++) {
        if (b&mask) bit_b = 1;
        else bit_b = 0;
        if (c&mask) bit_c = 1;
        else bit_c = 0;
        if (d&mask) bit_d = 1;
        else bit_d = 0;
        if ((bit_b && (!bit_c) && (!bit_d)) || ((!bit_b) && bit_c && bit_d)) {
            pos = 0;
            break;
        }
        if (bit_b && bit_c) {
            a += (1ll-bit_d)*mask;
        } else {
            a += bit_d*mask;
        }
        mask<<=1;
    }
    if (pos) {
        cout << a << "\n";
    } else {
        cout << -1 << "\n";
    }
}
 
int main() {
    ll t;
    cin >> t;
    while (t--) {
        solve();
    }
}