#1083741 (C++17) No.752 mod数列

• 問題: No.752 mod数列
• ユーザー: qwewe
• 提出日時: 2025-05-14 12:58:59
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: TLE
• 実行時間: -
• コード長: 7,326 bytes
• コンパイル時間: 515 ms
• コンパイル使用メモリ: 68,896 KB
• 実行使用メモリ: 16,072 KB
• 最終ジャッジ日時: 2025-05-14 13:00:14
• 合計ジャッジ時間: 5,510 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

ファイルパターン	結果
sample	-- * 3
other	AC * 16 TLE * 1 -- * 14

ソースコード

#include <iostream>

// Using unsigned __int128 for intermediate calculations to prevent overflow.
// The problem involves sums that can exceed the capacity of standard 64-bit integers (long long),
// especially during intermediate product calculations. `unsigned __int128` is a non-standard
// extension available in GCC and Clang that provides 128-bit integer arithmetic.
// The final results are expected to fit within a standard `long long`.

/**
 * @brief Computes the sum of P mod n for n in the range [L, R].
 * 
 * The sequence is defined as a_n = P mod n. We need to compute Sum_{n=L}^{R} a_n.
 * The calculation uses the identity P mod n = P - n * floor(P/n).
 * The sum is split into two parts: n <= P and n > P.
 * For n > P, P mod n = P.
 * For n <= P, we compute Sum (P - n * floor(P/n)) = (Count * P) - Sum (n * floor(P/n)).
 * The sum Sum (n * floor(P/n)) is computed efficiently using block summation based on the
 * observation that floor(P/n) takes on O(sqrt(P)) distinct values.
 * 
 * @param P The integer P used in the modulo operation.
 * @param L The start of the range (inclusive).
 * @param R The end of the range (inclusive).
 * @return The sum Sum_{n=L}^{R} (P mod n) as a long long.
 */
long long compute_sum_range(long long P, long long L, long long R) {
    // Handle invalid range where L > R. The sum is 0.
    if (L > R) return 0LL;

    // Use 128 bit integer type for accumulating the total sum to avoid potential overflow issues.
    unsigned __int128 total_sum_mod = 0; 

    // --- Part 1: Handle the portion of the range where n > P ---
    // If the entire range [L, R] is above P, then for all n in [L, R], P mod n = P.
    if (L > P) {
        // The sum is simply (R - L + 1) * P.
        // Use 128-bit types for calculation to avoid overflow if R-L+1 is large.
        unsigned __int128 count_gt_P = 0;
        // Ensure R >= L before calculating count to avoid underflow issues with unsigned types
        if (R >= L) count_gt_P = (unsigned __int128)(R - L + 1); 
        unsigned __int128 P_u128 = P;
        total_sum_mod = count_gt_P * P_u128;
        return (long long)total_sum_mod; // Cast the final result back to long long
    }

    // If the range [L, R] partially overlaps with n > P (i.e., L <= P < R)
    long long current_R = R; // Use current_R to track the upper bound for calculations involving n <= P
    if (R > P) {
        // Calculate the sum for n in the range [P+1, R]. For these n, P mod n = P.
        // The sum is (R - (P+1) + 1) * P = (R - P) * P.
        unsigned __int128 count_gt_P = (unsigned __int128)(R - P);
        unsigned __int128 P_u128 = P;
        total_sum_mod += count_gt_P * P_u128; 
        current_R = P; // Adjust the upper bound to P for the subsequent calculation part
    }

    // --- Part 2: Handle the portion of the range where n <= P ---
    // Now we need to compute the sum for n in the range [L, current_R], where current_R <= P.
    
    long long current_L = L; // Start from the original L
    // Ensure current_L is at least 1, as the problem constraints state L >= 1.
    // This also prevents potential issues with division by zero if P/n is calculated for n=0.
    if (current_L < 1) current_L = 1; 
    
    // If after adjustments (like L starting > P, or R being adjusted down to P),
    // current_L becomes greater than current_R, it means this part of the range is empty.
    // We just return the sum accumulated so far (from the n > P part, if any).
    if (current_L > current_R) {
         return (long long)total_sum_mod;
    }

    // Use the formula: Sum_{n=current_L}^{current_R} (P mod n) = Sum_{n=current_L}^{current_R} (P - n * floor(P/n))
    // Which expands to: (current_R - current_L + 1) * P - Sum_{n=current_L}^{current_R} n * floor(P/n)
    
    // We compute Sum_{n=current_L}^{current_R} n * floor(P/n) using block summation.
    unsigned __int128 sum_n_floor_Pn = 0; // Accumulator for the sum n * floor(P/n) part
         
    long long n = current_L; // Start iterating from current_L
    while (n <= current_R) {
        // Calculate k = floor(P/n). Since n is constrained current_L <= n <= current_R <= P,
        // and P >= 1, n >= 1, k will always be >= 1. Division by zero is not possible.
        long long k = P / n;
        
        // Find the largest n' in the range [n, current_R] such that floor(P/n') = k.
        // This is given by floor(P/k).
        long long n_max_for_k = P / k; // Safe division since k >= 1
        
        // The current block ends at min(current_R, n_max_for_k).
        long long n_end = current_R < n_max_for_k ? current_R : n_max_for_k;

        // Compute the sum of the arithmetic series: Sum_{i=n}^{n_end} i
        // Formula: (count * (first + last)) / 2
        // Use 128-bit intermediate calculations for safety.
        unsigned __int128 first = n;
        unsigned __int128 last = n_end;
        unsigned __int128 count = 0;
        if (last >= first) count = last - first + 1; // Calculate count safely
        
        unsigned __int128 sum_arith_series = 0;
        if (count > 0) {
            // Use property that count * (first + last) is always even.
            // Perform division first where possible to mitigate overflow risk, although with 128-bit it's less critical.
            if (count % 2 == 0) {
                sum_arith_series = (count / 2) * (first + last);
            } else {
                // If count is odd, (first + last) must be even.
                sum_arith_series = count * ((first + last) / 2); 
            }
        }
        
        // Compute the contribution of this block: k * sum_arith_series
        unsigned __int128 term = (unsigned __int128)k * sum_arith_series;
        sum_n_floor_Pn += term; // Add to the accumulator sum_n_floor_Pn

        // Move to the start of the next block.
        // Check for potential infinite loop if n_end doesn't advance n.
        // This typically shouldn't happen with correct logic but serves as a safeguard.
        if (n_end < n) {
             break; // Should not occur, indicates a logic flaw if it does.
        }
        n = n_end + 1;
    }

    // Add the sum contribution from the range [current_L, current_R] to the total sum.
    unsigned __int128 P_u128 = P;
    unsigned __int128 count_le_P = 0;
    if (current_R >= current_L) count_le_P = (unsigned __int128)(current_R - current_L + 1);

    // total_sum_mod += (Sum P) - (Sum n*floor(P/n))
    total_sum_mod += count_le_P * P_u128 - sum_n_floor_Pn;

    // Return the final total sum, cast back to long long.
    return (long long)total_sum_mod;
}


int main() {
    // Use faster I/O operations
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    long long P; // The parameter P for the modulo sequence
    int Q;       // The number of queries
    std::cin >> P >> Q;

    // Process each query
    for (int i = 0; i < Q; ++i) {
        long long L, R; // Range for the current query
        std::cin >> L >> R;
        
        // Compute the sum for the query range [L, R]
        long long res = compute_sum_range(P, L, R);
        
        // Output the result for the current query
        std::cout << res << "\n"; // Use "\n" instead of std::endl for potentially faster output flushing
    }
    
    return 0; // Indicate successful execution
}