Nội dung Bài tập
- Mã:
-
MINIGAME44.3:
NTCN
- Tên:
- Nguyên tố cùng nhau
- Dạng thi:
- oi
- Thang điểm:
- 30 điểm
- Giới hạn thời gian:
- 10 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- admin
Hiếu mong muốn sẽ xây dựng được một phương thức mã hoá thông tin mới có độ an toàn gần như tuyệt đối. Phương thức mã hoá này được phát triển dựa trên ý tưởng về tập hợp các số nguyên tố cùng nhau.
Quảng cáo
Bước đầu tiên của nghiên cứu là: “Từ một tập hợp các số nguyên dương S, Hiếu muốn chọn ra một tập con S' có số phần tử nhiều nhất sao cho hai số bất kì trong tập con S' luôn nguyên tố cùng nhau”.
Bạn hãy lập trình giúp Hiếu giải quyết vấn đề đơn giản này để Hiếu tập trung làm những phần việc quan trọng hơn.
Input:
- Dòng đầu tiên ghi số một số nguyên n (n<= 5000) là số lượng các số thuộc tập hợp S.
- Dòng thứ i trong n dòng tiếp theo ghi một số nguyên dương là số thứ i của S.
Output:
- Ghi ra một số nguyên là kích thước lớn nhất của tập con S' của S mà hai số bất kì thuộc S' nguyên tố cùng nhau
Ví dụ:
Input Output
Ràng buộc:
- Có 1/7 số test: các số thuộc tập không vượt quá 20
- Có 3/7 số test: các số thuộc tập không vượt quá 100.
- Có 3/7 số test còn lại các số thuộc tập không vượt quá 5000.
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
#include <iostream>using namespace std;struct ps { int tu, mau; &...