結果

問題 No.1946 ロッカーの問題
ユーザー qwewe
提出日時 2025-05-14 12:57:05
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 24 ms / 3,000 ms
コード長 4,169 bytes
コンパイル時間 471 ms
コンパイル使用メモリ 74,352 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2025-05-14 12:58:55
合計ジャッジ時間 1,586 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric> // Included for completeness, though not used directly for algorithms like accumulate.

int main() {
    // Optimize standard I/O operations for faster execution.
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int N; // Number of students and lockers
    int M; // Number of lockers that are open at the end
    std::cin >> N >> M;
    
    // Create a vector `f` to store the final state of the lockers.
    // f[j] = 1 if locker j is open, 0 if closed.
    // We use size N+1 to allow 1-based indexing, matching the problem statement (lockers 1 to N).
    // Initialize all lockers to closed (0).
    std::vector<int> f(N + 1, 0); 
    for (int i = 0; i < M; ++i) {
        int A_i; // Read the number of an open locker
        std::cin >> A_i;
        // Basic validation: Ensure the locker number is within the valid range [1, N].
        if (A_i >= 1 && A_i <= N) {
             f[A_i] = 1; // Mark this locker as open in the final state vector.
        }
    }
    
    // Create a vector `p` to store the ideal final state of the lockers if no student skipped.
    // p[j] = 1 if locker j would be open, 0 if closed.
    // Locker j is toggled by student i if j is a divisor of i (which means i is a multiple of j).
    // The total number of students who toggle locker j is floor(N/j).
    // Locker j ends up open if floor(N/j) is odd, and closed if it's even.
    // So, p[j] is the parity of floor(N/j).
    std::vector<int> p(N + 1, 0); 
    for (int j = 1; j <= N; ++j) {
        // Integer division `N / j` in C++ computes floor(N/j).
        p[j] = (N / j) % 2; // Compute the parity.
    }
    
    // Create a vector `k` based on the actual final state `f` and the ideal final state `p`.
    // k[j] represents the parity of the number of students who skipped among those supposed to operate locker j.
    // The relationship is derived as: f[j] = (p[j] + k[j]) mod 2.
    // Rearranging gives: k[j] = (f[j] + p[j]) mod 2 (since subtraction is addition in modulo 2).
    std::vector<int> k(N + 1, 0); 
    for (int j = 1; j <= N; ++j) {
        k[j] = (f[j] + p[j]) % 2; // Calculate k[j] for each locker.
    }
    
    // Create a vector `s` to determine which students skipped.
    // s[i] = 1 if student i skipped their turn, 0 otherwise.
    // We compute s[i] using a relationship derived from the problem setup, which forms a system of linear equations over GF(2).
    // The relationship can be expressed recursively: s_j = (k_j + Sum_{m=multiple of j, m > j, m <= N} s_m) mod 2.
    // We compute s[j] iteratively starting from j=N down to j=1.
    std::vector<int> s(N + 1, 0); 
    int skipped_count = 0; // Initialize counter for the total number of skipped students.
    
    // Iterate from student N down to student 1.
    for (int j = N; j >= 1; --j) {
        int current_sum_mod2 = 0; // Accumulator for the sum part of the formula, calculated modulo 2.
        
        // Calculate Sum_{m=kj, k>=2, m<=N} s[m] mod 2
        // Loop through multiples m = 2j, 3j, ... up to N.
        // Use `long long` for `m` in loop initialization and update `m += j` to prevent potential intermediate overflow, 
        // especially if N is close to the maximum value of `int`. `2LL * j` forces `long long` multiplication.
        for (long long m = 2LL * j; m <= N; m += j) {
             // Since `m > j`, `s[m]` would have been computed in previous iterations (for indices greater than j).
             // We add `s[m]` to the sum. The index `m` is at most N, safely castable to `int` for vector access.
             current_sum_mod2 = (current_sum_mod2 + s[static_cast<int>(m)]) % 2; 
        }
        
        // Compute s[j] using the derived recursive formula.
        s[j] = (k[j] + current_sum_mod2) % 2;
        
        // If s[j] is 1, it signifies that student j skipped their turn. Increment the count.
        if (s[j] == 1) {
            skipped_count++;
        }
    }
    
    // Output the final computed total number of skipped students.
    std::cout << skipped_count << std::endl;
    
    return 0; // Indicate successful execution.
}
0