(7 ĐIỂM)MỘT DÃY SỐ NGUYÊN A

Bài 2: (7 điểm)

Một dãy số nguyên A: a

1

, a

2

,..., a

N

được gọi là dãy chia hết hoàn toàn nếu A có ít nhất 2

phần tử và mọi phần tử a

j

đều chia hết cho tất cả các phần tử a

i

đứng trước nó (1 ≤ i < j ≤ N).

Một dãy con của A là một cách chọn ra trong A một số phần tử giữ nguyên thứ tự.

Yêu cầu: Viết chương trình nhập vào một dãy số nguyên A: a

1

, a

2

,..., a

N

. Tìm dãy con chia hết

hoàn toàn của A có độ dài lớn nhất.

Ví dụ 1: Dãy A: 3, 5, 9, 7, 15, 18, 35, 54. Dãy con chia hết hoàn toàn dài nhất là: 3, 9, 18, 54.

Ví dụ 2: Dãy A: 6, 9, 15. Không tìm được dãy con chia hết hoàn toàn.

Dữ liệu vào: Cho trong file văn bản MULSEQ.IN gồm 2 dòng:

 Dòng đầu tiên chứa số nguyên dương N (1 ≤ n ≤ 5000), là số lượng phần tử của dãy A.

 Dòng thứ hai gồm N số nguyên a

1

, a

2

,..., a

N

( -10000 ≤ a

i

≤ 10000), các số được viết

cách nhau ít nhất một dấu cách.

Dữ liệu ra: Ghi ra file văn bản MULSEQ.OU:

- Nếu tìm được dãy con chia hết hoàn toàn thì file MULSEQ.OU gồm 2 dòng:

o Dòng đầu ghi độ dài của dãy con chia hết hoàn toàn dài nhất tìm được.

o Dòng thứ hai ghi các phần tử được chọn vào dãy con này.

- Nếu không tìm được dãy con chia hết hoàn toàn thì file MULSEQ.OU ghi số -1.

Ví dụ 1 Ví dụ 2

MULSEQ.IN MULSEQ.OU MULSEQ.IN MULSEQ.OU

8

4

3

-1

3 5 9 7 15 18 35 54

3 9 18 54

6 9 15

Trang 1 - đề thi gồm có 2 trang ..