Sum Multiples of Three, Five, or Seven

Problem Statement

Given a positive integer n, calculate the sum of all distinct positive integers strictly less than n that are divisible by 3, 5, or 7.

Because n can be as large as 10^18, an iterative approach checking each number will exceed the time limit. Your solution should run in O(1) time.

Function Signature

def sum_multiples(n: int) -> int:
    pass

Constraints

• 1 <= n <= 10^18
• The return value fits within standard arbitrary-precision integers (in Python) or requires 128-bit integer handling in languages like C++/Java.

Examples

Example 1:

Input: n = 12
Output: 40
Explanation:
The positive integers strictly less than 12 divisible by 3, 5, or 7 are:
- Multiples of 3: 3, 6, 9
- Multiples of 5: 5, 10
- Multiples of 7: 7
No number is repeated among these. Sum = 3 + 6 + 9 + 5 + 10 + 7 = 40.
Note that 12 is excluded because the integers must be strictly less than n.

Example 2:

Input: n = 20
Output: 119
Explanation:
Distinct multiples below 20:
- Divisible by 3: 3, 6, 9, 12, 15, 18
- Divisible by 5: 5, 10, 15
- Divisible by 7: 7, 14
The value 15 appears in both the 3 and 5 lists and must be counted only once.
Sum = 3 + 5 + 6 + 7 + 9 + 10 + 12 + 14 + 15 + 18 = 119.

Edge Cases to Consider

• n <= 3: There are no positive integers strictly less than n divisible by 3, 5, or 7, so the result should be 0.
• Exact multiples of 3, 5, or 7: Ensure n itself is not included in the sum when n is divisible by one of the divisors.