Giao Hai Cấp Số Cộng · canuc80k5416

Xét hai cấp số cộng gồm các giá trị $a_{1} \cdot t + b_{1}$ và $a_{2} \cdot u + b_{2}$ , trong đó $t, u$ là các số nguyên không âm.

Hãy đếm bao nhiêu số nguyên trong đoạn đóng $[L, R]$ xuất hiện trong cả hai cấp số.

Input

Một dòng chứa $a_{1}$ $b_{1}$ $a_{2}$ $b_{2}$ $L$ $R$ .

Output

In số lượng số nguyên thuộc cả hai cấp số trong đoạn đã cho.

Constraints

$1 \leq a_{1}, a_{2} \leq 2 \cdot 1 0^{9}$ .
$- 2 \cdot 1 0^{9} \leq b_{1}, b_{2}, L, R \leq 2 \cdot 1 0^{9}$ .
$L \leq R$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $a_{1}, a_{2} \leq 1000$ .
Subtask $2$ ( $50%$ số điểm): không có giới hạn bổ sung.

Example

Test 1

Input

3 1 4 2 -10 30

Output

Giải thích: Các giá trị chung trong đoạn là $10$ và $22$ ; cả hai đều có dạng $3 t + 1$ và $4 u + 2$ với chỉ số không âm. Vì vậy đáp án bằng $2$ .

Mô hình: Xét hai cấp số cộng gồm các giá trị a_1·t + b_1 và a_2·u + b_2, trong đó t, u là các số nguyên không âm.
Mô hình: Nhiệm vụ là đếm bao nhiêu số nguyên trong đoạn đóng [L, R] xuất hiện trong cả hai cấp số.
Thuật toán: Một z thuộc cấp số thứ nhất khi z≡b1 (mod a1) và z>=b1; tương tự cho cấp số thứ hai. Ghép:
Thuật toán: z ≡ b1 (mod a1), z ≡ b2 (mod a2).
Thuật toán: Nếu vô nghiệm, đáp án 0. Nếu có z≡r (mod M), cận dưới thực là
Thuật toán: low=max(L,b1,b2).
Thuật toán: Tìm t nhỏ nhất sao cho r+M*t>=low:
Thuật toán: t=ceil((low-r)/M).
Thuật toán: Phải tự viết ceil_div đúng cho số âm. first=r+M*t; nếu first>R thì 0, ngược lại đáp án floor((R-first)/M)+1. Dùng __int128 cho hiệu và phép nhân.
Chứng minh đúng đắn: Điều kiện đồng dư là cần và đủ cho z nằm trên đường thẳng vô hạn của từng cấp số; điều kiện k,l>=0 tương đương z>=b1,b2 vì bước dương. Do đó các z cần đếm chính xác là lớp CRT cắt với đoạn [low,R]. first là phần tử đầu tiên của lớp không nhỏ hơn low, và mọi phần tử sau cách M, nên công thức đếm đúng.
Độ phức tạp: O(log max(a1,a2)); O(1) bộ nhớ.
Lỗi thường gặp: Bỏ cận z>=b1,b2, vô tình cho phép chỉ số cấp số âm.
Lỗi thường gặp: Dùng (x+M-1)/M khi x âm.
Lỗi thường gặp: Tràn khi tính r+Mt dù input chỉ 210^9.