Elearning CodePath – CTP Online Judge

Trồng cây

GEN023

🟢 Hard #General

### CÂU 2: TRỒNG CÂY [CAU2]

#### 📌 Thông tin chung

---
#### 📝 Bài toán

Có các hố trồng cây được đánh chỉ số $1, 2, 3, \dots$.

1.  **Lớp 9A:** Trồng vào các hố $i$ thỏa mãn: $a \le i \le b$ và $i$ chia hết cho $k$ ($i \equiv 0 \pmod k$).
    * Tập hợp $A = \{i \mid a \le i \le b, i \equiv 0 \pmod k\}$.
2.  **Lớp 9B:** Trồng vào các hố $j$ thỏa mãn: $c \le j \le d$, $j$ chia hết cho $q$ ($j \equiv 0 \pmod q$) và hố $j$ chưa có cây (tức là $j \notin A$).
    * Tập hợp $B = \{j \mid c \le j \le d, j \equiv 0 \pmod q, j \notin A\}$.

Xác định tổng số cây hai lớp trồng được: $|A| + |B|$.
Do $B$ không chứa các hố đã trồng bởi $A$, tổng số cây là:
$\text{Tổng cây} = |A| + |B| = |A| + |\{j \mid c \le j \le d, j \equiv 0 \pmod q\}| - |A \cap B'|$
Với $B' = \{j \mid c \le j \le d, j \equiv 0 \pmod q\}$.

---
#### 📥 Định dạng Đầu vào

* Dòng 1: Ba số nguyên $a, b, k$.
* Dòng 2: Ba số nguyên $c, d, q$.

Giới hạn:
* $0 < a \le b < 10^6$.
* $0 < c \le d < 10^6$.
* $0 < k, q \le 100$.

---
#### 📤 Định dạng Đầu ra

* Dòng 1: Số nguyên duy nhất là tổng số cây hai lớp trồng được.

---
#### 🏷 Phân tích Thuật toán

**1. Tính $|A|$: Số cây lớp 9A trồng.**
* Số $i$ nhỏ nhất $\ge a$ và chia hết cho $k$: $i_{\min} = \lceil \frac{a}{k} \rceil \times k$.
* Số $i$ lớn nhất $\le b$ và chia hết cho $k$: $i_{\max} = \lfloor \frac{b}{k} \rfloor \times k$.
* $|A| = \lfloor \frac{b}{k} \rfloor - \lceil \frac{a}{k} \rceil + 1$.
* **Hoặc đơn giản hơn:** $|A| = \lfloor \frac{b}{k} \rfloor - \lfloor \frac{a-1}{k} \rfloor$.

**2. Tính $|B'|$: Số hố tiềm năng lớp 9B trồng (chưa xét điều kiện trùng).**
* $B' = \{j \mid c \le j \le d, j \equiv 0 \pmod q\}$.
* $|B'| = \lfloor \frac{d}{q} \rfloor - \lfloor \frac{c-1}{q} \rfloor$.

**3. Tính $|A \cap B'|$: Số hố trùng nhau (cả hai lớp đều trồng).**
* $i \in A \cap B' \iff i$ thỏa mãn:
    * $\max(a, c) \le i \le \min(b, d)$
    * $i$ chia hết cho $k$ và $i$ chia hết cho $q$.
* Điều kiện chia hết cho $k$ và $q$ tương đương với chia hết cho $\text{BCNN}(k, q)$.
* Đặt $L = \text{BCNN}(k, q) = \frac{k \times q}{\text{ƯCLN}(k, q)}$.
* $i \in A \cap B' \iff \max(a, c) \le i \le \min(b, d)$ và $i \equiv 0 \pmod L$.
* $|A \cap B'| = \lfloor \frac{\min(b, d)}{L} \rfloor - \lfloor \frac{\max(a, c) - 1}{L} \rfloor$.

**4. Kết quả cuối cùng:**
$\text{Tổng cây} = |A| + (|B'| - |A \cap B'|)$

✅ Đã AC: 0 / 1 submissions