To solve this problem, we need to determine the number of integers within a given range [L, R] that are multiples of both integers a and b.

Approach

1. Understanding Multiples: A number that is a multiple of both a and b must be a multiple of their Least Common Multiple (LCM).
2. Calculate LCM: The LCM of two numbers a and b can be computed using their Greatest Common Divisor (GCD) with the formula:
   ( LCM(a, b) = \frac{a \times b}{GCD(a, b)} )
3. Count Multiples: Once we have the LCM, the number of multiples of LCM in the range [L, R] is given by:
   ( \text{count} = \left\lfloor \frac{R}{LCM} \right\rfloor - \left\lfloor \frac{L-1}{LCM} \right\rfloor )
   This formula works because it counts all multiples up to R and subtracts the count of multiples up to L-1, leaving the count of multiples in the desired range.

Solution Code

import math

a, b, L, R = map(int, input().split())
gcd_val = math.gcd(a, b)
lcm_val = (a * b) // gcd_val
count = (R // lcm_val) - ((L - 1) // lcm_val)
print(count)

Explanation

1. GCD Calculation: We use the math.gcd function to find the GCD of a and b. This helps in computing the LCM efficiently.
2. LCM Calculation: Using the GCD, we compute the LCM of a and b. This LCM is the smallest number that is a multiple of both a and b.
3. Counting Multiples: The count of multiples of the LCM in the range [L, R] is calculated by dividing R by LCM (to get the number of multiples up to R) and subtracting the number of multiples up to L-1 (to exclude numbers before L).

This approach is efficient and handles all edge cases, such as when the LCM is larger than R (resulting in zero multiples) or when L equals R (checking if L is a multiple of the LCM).

The time complexity of this solution is dominated by the GCD calculation, which is ( O(\log(\min(a, b))) ), making it very efficient even for large values of a and b. The rest of the operations are constant time, so the overall complexity is ( O(\log(\min(a, b))) ).

This solution should work correctly for all valid inputs as specified in the problem statement.

作者声明:本文包含人工智能生成内容。