Sum Pairwise Remainders Across Two Integer Ranges

Sum Pairwise Remainders Across Two Integer Ranges

Given two inclusive integer ranges [a_min, a_max] (representing dividends) and [d_min, d_max] (representing divisors), compute the sum of a % d for every pair (a, d) where a_min <= a <= a_max, d_min <= d <= d_max, and d != 0.

Division by zero is undefined, so any pair where d == 0 must be skipped.

Note that in standard mathematical modulo arithmetic (or language-specific conventions like Python's %), remainder properties can depend on signs. For this problem, assume all inputs are non-negative integers (>= 0), so a % d represents the standard non-negative remainder.

Because the resulting total can be large, ensure calculations avoid 32-bit integer overflow.

Function Signature

def sum_pairwise_remainders(a_min: int, a_max: int, d_min: int, d_max: int) -> int:
    pass

Constraints

• 0 <= a_min <= a_max <= 10^5
• 0 <= d_min <= d_max <= 10^5
• The total number of valid pairs evaluated will not exceed 10^7 for standard execution tests, but solutions should aim to be as efficient as possible.

Examples

Example 1:

Input: a_min = 5, a_max = 7, d_min = 2, d_max = 3
Output: 4

Explanation:

• For a = 5: 5 % 2 = 1, 5 % 3 = 2 (sum = 3)
• For a = 6: 6 % 2 = 0, 6 % 3 = 0 (sum = 0)
• For a = 7: 7 % 2 = 1, 7 % 3 = 1 (sum = 2)
• Total sum: 3 + 0 + 2 = 5? Wait: 1 + 2 + 0 + 0 + 1 + 1 = 5. Output is 5.

Example 2:

Input: a_min = 10, a_max = 10, d_min = 0, d_max = 4
Output: 3

Explanation:

• d = 0 is skipped.
• For a = 10: 10 % 1 = 0, 10 % 2 = 0, 10 % 3 = 1, 10 % 4 = 2.
• Total sum: 0 + 0 + 1 + 2 = 3.