Problem: back_in_black_ch1 (2023 round1)

*This problem shares some similarities with C2, with key differences in bold.*

A friend who works at Metal Platforms Inc just lent you a curious puzzle, offering you tickets to a metal concert if you can solve it.

The puzzle consists of \(N\) buttons in a row, numbered from \(1\) to \(N\). The initial state of button \(i\) is white if \(S_i = 1\), or black if \(S_i = 0\). Pressing a button \(k\) toggles the state of itself as well as every \(k\)th button. Your friend challenges you to return the puzzle to him with all buttons back in black.

Life is hard enough without siblings pushing your buttons. Unfortunately, your brother has taken the puzzle and will push \(Q\) buttons sequentially, the \(i\)th being button \(B_i\). 

After your brother **has pushed all \(Q\) buttons**, you'd like to know the minimum number of button presses required to turn all the buttons black.

**Constraints**

\(1 \le T \le 70\)
\(1 \le N \le 4{,}000{,}000\)
\(1 \le Q \le 4{,}000{,}000\)

The sum of \(N\) and \(Q\) over all cases will be at most \(9{,}000{,}000\).

**Input Format**

Input begins with a single integer \(T\), the number of test cases. For each case, there is first a line containing a single integer \(N\). Then, there is a line containing a bitstring \(S\) of length \(N\). Then, there is a line containing a single integer \(Q\). \(Q\) lines follow, the \(i\)th of which contains a single integer \(B_i\).

**Output Format**

For the \(i\)th test case, output a single line containing `"Case #i: "` followed by a single integer, the number of button presses needed to turn all buttons black **after all \(Q\) button presses.**

**Sample Explanation**

The first sample case is depicted below. After your brother presses the first button, the state of the puzzle is \(0101\). The best strategy is to press the second button, turning all lights off.

{{PHOTO_ID:287687020772716|WIDTH:400}}

In the second case, the puzzle starts as \(0001\), and after each button press becomes \(0100\), \(0110\), \(0011\), and \(0010\) respectively. Pressing only the third button will return the puzzle to all zeros.


Sample input:
5
4
1010
1
1
4
0001
4
2
3
2
4
7
0101101
8
1
3
2
6
7
4
2
5
7
0101100
1
7
7
1111111
1
1


Sample output:
Case #1: 1
Case #2: 1
Case #3: 4
Case #4: 4
Case #5: 0


Solution: First, note that pressing any button twice is equivalent to doing nothing. We can read in all \(Q\) button presses into a boolean array \(P_{1..N}\), where \(P_i\) stores for button \(i\) the total number of presses modulo \(2\).

Next, we'll need to apply this array of presses to our original array \(S_{1..N}\). Naively, it would look something like:
```
for (int i = 1; i <= N; i++) {
    if (P[i]) {
        for (int j = i; j <= N; j += i) {
            S[j] ^= 1;
        }
    }
}
```

For \(i = 1\), the inner loop runs for \(N\) steps. For \(i = 2\), the inner loop runs for \(N / 2\) steps. So forth, until a total of \(N + \frac{N}{2} + \frac{N}{3} + ... + \frac{N}{N}\) steps. Factoring out \(N\), we get \(N*(1 + \frac{1}{2} + ... + \frac{1}{N})\). The second factor is the [harmonic series](https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)), which converges to roughly \(\log_2 (N)\). Thus, such a nested loop would only take \(\mathcal{O}(N \log N)\) time.

After we've applied the presses to \(S\), we now need to convert every \(1\) to \(0\) with the minimum number of button presses. Consider the following greedy algorithm:

```
int num_presses = 0;
for (int i = 1; i <= N; i++) {
    if (S[i]) {
      num_presses++;
      for (int j = i; j <= N; j += i) {
        S[j] ^= 1;
      }
    }
}
```

We scan from left to right, and each time we see a \(1\), we'll simply press the button and apply the changes to the rest of the array. In fact, this is not a greedy method, but the only method we can convert all the buttons to \(0\). A button can only be changed by pressing itself, or some button before it. If it were not optimal to clear the leftmost \(1\) by pressing it directly, then we would have to press another \(1\) before it, which contradicts the former \(1\) being leftmost.

The time complexity of this approach algorithm is analyzed similarly as the original application of the \(Q\) button presses, so the overall running time is \(\mathcal{O}(N \log N)\).


Code: #include <iostream>
#include <vector>
using namespace std;

int solve() {
  int N, Q;
  cin >> N;
  vector<bool> white(N + 1);
  for (int i = 1; i <= N; i++) {
    char c;
    cin >> c;
    white[i] = c - '0';
  }
  vector<bool> press(N + 1);
  cin >> Q;
  for (int i = 0, b; i < Q; i++) {
    cin >> b;
    press[b] = press[b] ^ 1;
  }
  // Apply presses.
  for (int i = 1; i <= N; i++) {
    if (press[i]) {
      for (int j = i; j <= N; j += i) {
        white[j] = white[j] ^ 1;
      }
    }
  }
  // Convert to black greedily.
  int num_presses = 0;
  for (int i = 1; i <= N; i++) {
    if (white[i]) {
      num_presses++;
      for (int j = i; j <= N; j += i) {
        white[j] = white[j] ^ 1;
      }
    }
  }
  return num_presses;
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}