#include #include #include #include #include // Fast I/O void fast_io() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); } int main() { fast_io(); int N; std::cin >> N; std::vector A(N); for (int i = 0; i < N; ++i) { std::cin >> A[i]; } int Q_count; std::cin >> Q_count; std::vector queries_X(Q_count); // X_i up to 10^9, fits in int for (int i = 0; i < Q_count; ++i) { std::cin >> queries_X[i]; } int B = static_cast(sqrt(N)); if (B == 0) { // Handles N=0, though N >= 1 from constraints. If N=1, B=1. B = 1; } int num_blocks = (N + B - 1) / B; std::vector block_sum(num_blocks); std::vector block_max_val(num_blocks); // Lambda to initialize/recompute a block's sum and max value auto recompute_block_info = [&](int block_idx) { long long current_sum_for_block = 0; long long current_max_for_block = 0; int start_idx = block_idx * B; int end_idx = std::min((block_idx + 1) * B, N); // Correctly handle last block for (int j = start_idx; j < end_idx; ++j) { current_sum_for_block += A[j]; if (A[j] > current_max_for_block) { current_max_for_block = A[j]; } } block_sum[block_idx] = current_sum_for_block; block_max_val[block_idx] = current_max_for_block; }; // Initial computation of block summaries for (int i = 0; i < num_blocks; ++i) { recompute_block_info(i); } std::vector results; results.reserve(Q_count); // Pre-allocate space for results for (int qi = 0; qi < Q_count; ++qi) { long long current_X = queries_X[qi]; // Use long long for X in case it's used with A[j] extensively, though int is fine. // Modulo operand X_i constraint is int. long long current_total_sum_for_query = 0; for (int i = 0; i < num_blocks; ++i) { if (block_max_val[i] < current_X) { // All elements in this block are < X. No change to A[j] or block_sum. current_total_sum_for_query += block_sum[i]; } else { // At least one element in block MIGHT be >= X (or max_val itself is). // Iterate through this block, update elements, and recompute sum/max for block. int start_idx = i * B; int end_idx = std::min((i + 1) * B, N); for (int j = start_idx; j < end_idx; ++j) { if (A[j] >= current_X) { A[j] = A[j] % current_X; } } // Recompute sum and max for this modified block recompute_block_info(i); current_total_sum_for_query += block_sum[i]; } } results.push_back(current_total_sum_for_query); } for (long long res : results) { std::cout << res << "\n"; } return 0; }