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();
    }
}

The value of $$$d$$$ is very small.

Try using Disjoint Set Union (DSU).

The main idea is to take advantage of the low upper bound of $$$d_i$$$ and apply the Disjoint Set Union.

We will consider $$$dp[j][w]$$$, which denotes the number of ranges that contain the $$$j$$$ node in connection by the triplets/ranges with $$$w$$$ as $$$d$$$ and $$$j$$$ is not $$$a\ +\ k\ *\ d$$$, and $$$id[j][w]$$$, which denotes the node that represents an overall connected component of which $$$j$$$ node is part of for now.

The size of both $$$dp$$$ and $$$id$$$ is $$$max_j * max_w = (n) * 10 = 10\ n$$$.

We will maintain two other arrays, $$$Start_cnt[j][w]$$$ and $$$End_cnt[j][w]$$$, which store the number of triplets with $$$j$$$ as $$$a_i$$$ and $$$a_i+k_i*d_i$$$, respectively, and with $$$w$$$ as $$$d_i$$$, to help us maintain the beginning and end of ranges.

We will now apply Disjoint Set Union. For each $$$i$$$th triplet, we assume $$$a_i$$$ will be the parent node of the Set created by $$$a_i$$$, $$$a_i$$$ + $$$d_i$$$, ..., $$$a_i+k_i*d_i$$$.

The transitions of $$$dp$$$ are as follows:

1) if $$$j \ge 10$$$ (max of $$$d_i$$$): for all $$$w$$$, $$$dp[j][w]$$$ are the same as $$$dp[j-w][w]$$$, just with some possible changes. These changes are due to $$$j$$$ being the start or the end of some triplet with $$$d_i$$$ as $$$w.$$$ So, let us start with $$$dp[j][w]$$$ as $$$Start_cnt[j][w] - End_cnt[j][w]$$$. If $$$dp[j-w][w]$$$ is non-zero, then perform a union operation (of DSU) between the $$$j$$$ node and $$$id[j-w][w]$$$, increment $$$dp[j][w]$$$ by $$$dp[j-w][w]$$$, and assign $$$id[j][w]$$$ as $$$id[j-w][w]$$$. This unites the ranges over the $$$j$$$ node.

2) if $$$j \lt 10$$$ (max of $$$d_i$$$): we do the same as above; rather than doing for all $$$w,$$$ we would restrict ourselves with $$$w$$$ from $$$0$$$ to $$$j-1$$$.

The net time complexity = updation of $$$dp[j][w]$$$ value by $$$Start_cnt$$$ and $$$End_cnt$$$ + union operations due to union of $$$id[j-w][w]$$$ with $$$j$$$ over all $$$w$$$ + incrementing $$$dp$$$ values (by $$$dp[j-w][w]$$$) + copying $$$id$$$ values = $$$10\ n + 10\ nlogn + 10\ n + 10\ n= 10 nlogn + 30n$$$ (in worst case) = $$$O(max_d*n*logn)$$$

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 2e5+2;
const ll C = 10 + 1;
 
vector<ll> par(N), sz(N, 0);
vector<vector<ll>> dp(N, vector<ll> (C, 0)), ind(N, vector<ll> (C, 0)), start_cnt(N, vector<ll> (C, 0)), end_cnt(N, vector<ll> (C,0));
 
ll find_par(ll a) {
    if (par[a] == a) return a;
    return par[a] = find_par(par[a]);
}
 
void unite(ll a, ll b){
    a = find_par(a), b = find_par(b);
    if (a == b) return;
    if (sz[b] > sz[a]) swap(a, b);
    sz[a] += sz[b];
    par[b] = a;
}
 
void reset(ll n) {
    for (ll i = 1; i <= n; i++) {
        par[i] = i;
        sz[i] = 1;
        for (ll j = 1; j < C; j++) {
            dp[i][j] = start_cnt[i][j] = end_cnt[i][j] = 0;
            ind[i][j] = i;
        }
    }
}
 
void solve() {
    ll n, m, a, d, k;
    cin >> n >> m;
    reset(n);
    for (ll i = 0; i < m; i++) {
        cin >> a >> d >> k;
        start_cnt[a][d]++;
        end_cnt[a + k * d][d]++;
    }
    for (ll i = 1; i <= n; i++) {
        for (ll j = 1; j < C; j++) {
            dp[i][j] = start_cnt[i][j] - end_cnt[i][j];
            if (i-j < 1) continue;
            if (dp[i-j][j]) {
                unite(ind[i-j][j], i);
                ind[i][j] = ind[i-j][j];
                dp[i][j] += dp[i-j][j];
            }
        }
    }
    ll ans = 0;
    for (ll i = 1; i <= n; i++) {
        if (find_par(i) == i) ans++;
    }
    cout << ans << "\n";
}
 
int main() {
    ll t;
    cin >> t;
    while (t--) {
        solve();
    }
}