EZ1 - EZ AF 1
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 5.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: yurilover172

Cho 2 dãy A, B, mỗi dãy gồm N số nguyên dương. Dựng đồ thị hai phía như sau:

- Phần X gồm các số thuộc dãy A.

- Phần Y gồm các số thuộc dãy B.

- Có cạnh nối Ai với Bj nếu GCD(Ai, Bj) > 1.

Hãy tính số cạnh trong bộ ghép cực đại của đồ thị hai phía trên.

Giới hạn: N ≤ 105. Ai ≤ 109.

Dữ liệu vào:

- Dòng đầu tiên ghi số nguyên dương N.

- Dòng thứ hai ghi N số nguyên dương biểu diễn dãy A.

- Dòng thứ ba ghi N số nguyên dương biểu diễn dãy B.

Dữ liệu ra: một số nguyên duy nhất là kết quả bài toán trên.

Ví dụ

  • input
    2
    2 4
    3 6
    output
    1
Back to Top