VOSMUL - Sinh nhật của Benjamin
Giới hạn- Thời gian: 2.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Hôm nay là sinh nhật Benjamin, thầy giáo Brogan tặng cậu 3 dãy số A , B và C . Dãy A có N phần tử còn dãy B và C thì có M phần tử. Từ dãy B và C ta thu được số K như sau:
K = B 1 ^C 1 * B 2 ^C 2 * B 3 ^C 3 * B 4 ^C 4 * ... * B M ^C M
Dãy số B có tính chất là các phần tử khác nhau đôi một và mỗi phân tử là một số nguyên tố. Ngoài ra các phần tử trong dãy số A , B và C đều là số nguyên dương. Benjamin sẽ nhận thêm một món quà với trị giá bằng số lượng dãy con liên tiếp đặc biệt của A mà Benjamin tìm được. Một dãy số được coi là đặc biệt nếu tích các phần tử của nó chia hết cho K . Vì đây là các dãy số ngẫu nhiên mà thầy Brogan nghĩ ra nên thầy muốn biết giá trị phần thưởng lớn nhất là bao nhiêu để còn chuẩn bị quà cho Benjamin.
DỮ LIỆU VÀO
- Dòng đầu chứa số N và M.
- Dòng thứ hai chứa N số mô tả dãy A.
- M dòng tiếp theo, dòng thứ i chứa 2 số nguyên dương Bi và Ci.
DỮ LIỆU RA
- Gồm một dòng chứa kết quả bài toán.
RÀNG BUỘC
- N, M <= 10^5.
- A i , B i , C i <= 10^9.
- 30% số test N <= 1000.
VÍ DỤ
Dữ liệu vào:
4 2
1 2 3 4
2 1
3 1
Dữ liệu ra:
5
- Người up: yellowflash12
- Nguồn bài: VOS Round 28 - Trần Phan Anh Khoa