Problem Understanding

This problem simulates an operation process where m people interact with n light bulbs. Initially, all bulbs are in the ON state (represented by '1' for ON and '0' for OFF). The operations follow these rules:

Person 1: Turns off all bulbs (all states become 0).

Person 2: Toggles bulbs whose numbers are multiples of 2 (0 becomes 1, 1 becomes 0).

Person 3 and beyond: Toggle bulbs whose numbers are multiples of their own person number.

The goal is to count how many bulbs remain in the ON state (value 1) after all operations.

Solution Approach

Initialization: Use an array operations to track how many times each bulb gets toggled. Since all bulbs start ON, but Person 1 turns them all OFF, we consider this as the first operation setting all bulbs to OFF state. Subsequent operations toggle specific numbered bulbs.

Operation Process: For each person i (from 1 to m), they operate on bulbs that are multiples of i. Each operation increments the counter for that particular bulb in operations[j].

State Determination: A bulb's final state depends on the number of times it was operated. Even number of operations means no net change from initial state (ON, OFF, ON, etc.). Odd operations result in the opposite state. Since initial state is ON (1), and after first operation becomes OFF (0), the parity of operation counts determines final bulb status:

• Odd operations: bulb is OFF (0)
• Even operations: bulb is ON (1)

Result Calculation: Iterate through all bulbs and count those with even operation counts.

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

int main() {
    int bulbCount, personCount, activeBulbs = 0;
    cin >> bulbCount >> personCount;
    
    vector<int> operations(bulbCount + 1, 0); // Track operation count per bulb
    
    for (int person = 1; person <= personCount; person++) {
        for (int bulb = 1; bulb <= bulbCount; bulb++) {
            if (bulb % person == 0) { // If bulb number is multiple of person number
                operations[bulb]++; // Increment operation count
            }
        }
    }
    
    for (int idx = 1; idx <= bulbCount; idx++) {
        if (operations[idx] % 2 == 0) { // Even operations mean bulb remains ON
            activeBulbs++;
        }
    }
    
    cout << activeBulbs;
    return 0;
}