Sinh test GCD/LCM
Đề bài
Mô tả
Nam được giao nhiệm vụ sinh test cho bài toán sau:
Cho một dãy gồm số nguyên dương. Gọi là dãy trước khi thực hiện các truy vấn.
Thực hiện truy vấn thuộc một trong ba dạng như sau:
- "": với mọi .
- "": với mọi .
- "": Cho biết với mọi trong đoạn thì hay không?
Để sinh một bộ test tốt, với mỗi truy vấn loại , Nam cần biết có bao nhiêu cách điền giá trị vào sao cho thỏa mãn điều kiện đã cho.
Hãy giúp Nam giải quyết bài toán mới này.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên dương , () tương ứng với độ dài dãy và số truy vấn.
- Mỗi dòng trong dòng tiếp theo chứa một truy vấn như trên đề bài (, , ).
Dữ liệu ra
Với mỗi truy vấn loại , gọi là số bộ giá trị có thể điền vào sao cho thỏa điều kiện của truy vấn. Nếu thì in , ngược lại in . Mỗi kết quả in trên một dòng.
Ràng buộc
- .
- , , .
Subtasks
- Subtask 1 ( điểm): , , .
- Subtask 2 ( điểm): Không có truy vấn loại , .
- Subtask 3 ( điểm): Không có truy vấn loại .
- Subtask 4 ( điểm): .
- Subtask 5 ( điểm): .
- Subtask 6 ( điểm): Không có giới hạn gì thêm.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 6 CHK 2 4 LCM 1 1 10 1 GCD 1 3 9 1 GCD 1 5 9 5 CHK 1 3 CHK 1 5 |
-1 27 3267 |
Truy vấn CHK đầu tiên: chưa có thao tác nào nên mọi giá trị đều thỏa mãn, có vô số cách, in . Truy vấn CHK thứ hai: mỗi với phải thuộc , có cách. Truy vấn CHK thứ ba: thêm là ước của , mỗi số có cách, tổng cộng . |
| 4 7 GCD 1 4 12 1 CHK 1 4 LCM 2 3 2 1 GCD 4 4 2 3 CHK 1 4 LCM 1 1 3 1 CHK 1 2 |
1296 288 12 |
Ví dụ bổ sung (không có trên VNOJ). Lúc đầu mỗi phải là ước của : cách, . Sau đó phải là ước của chia hết cho ( cách), ( cách): . Cuối cùng phải là ước của chia hết cho ( cách): . |
Bình luận