Xóa số (THTB N.An 2021)

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Small
Dạng bài
Điểm: 1200 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Cho một dãy số nguyên dương gồm \(N\) phần tử. Từ dãy số đó, hãy xoá đi ít phần tử nhất để các phần tử còn lại thoả mãn tính chất sau: với mỗi hai phần tử \(x, y\) bất kì trong dãy còn lại, \(x\) chia hết cho \(y\) hoặc \(y\) chia hết cho \(x\).

Yêu cầu: Cho dãy số nguyên gồm \(N\) phần tử, đếm số lượng phần tử cần xoá đi ít nhất để thoả mãn yêu cầu bài toán.

Input

Vào từ thiết bị nhập chuẩn theo khuôn dạng:

  • Dòng đầu tiên chứa số nguyên dương \(N\);
  • Dòng thứ hai chứa \(N\) số nguyên dương, các số cách nhau bởi dấu cách và có giá trị không vượt quá \(10^6\).

Output

  • Ghi ra thiết bị ra chuẩn một số nguyên duy nhất – số lượng phần tử cần xoá đi ít nhất để thoả mãn yêu cầu bài toán.

Scoring

  • Subtask #1 (\(50\%\) số điểm): \(N \leq 20\);
  • Subtask #2 (\(30\%\) số điểm): \(N \leq 5000\);
  • Subtask #3 (\(20\%\) số điểm): \(N \leq 10^6\);

Example

Test 1

Input 
5
6 16 3 2 4
Output 
2
Note

Có thể xoá đi 2 số 6 và 3. Dãy còn lại: 16, 2, 4 đảm bảo tính chất mỗi hai phần tử \(x\) và \(y\) bất kì, \(x\) chia hết cho \(y\) hoặc \(y\) chia hết cho \(x\).

Bình luận