Không tương đồng (TS10 QT 2023)

Xem PDF

Nộp bài

Điểm: 1100 (thành phần)
Thời gian: 1.0s
Bộ nhớ: 256M
Input: CAU3.INP
Output: CAU3.OUT

Tác giả:
Dạng bài

Hai số nguyên dương n và m được gọi là hai số không tương đồng khi chúng khác nhau và không tồn tại hai số nguyên dương p,q (p\ne 1,q\ne 1,p\ne q) sao cho cả p và q đều là ước của cả n và m. Ví dụ: 6 và 8 là hai số không tương đồng bởi chúng chỉ có 2 số 1,2 là ước của cả hai số (6 và 8), nhưng chỉ có 1 số khác 1; 12 và 18 không phải là hai số không tương đồng vì có đến ba số khác 1 là 2,3,6 đều là ước của cả hai số

Yêu cầu: Cho số n và 2 số nguyên dương l,r. Hãy tìm tất cả các số m với l\le m\le r sao cho n với m là hai số không tương đồng

Input, Output và Subtasks

Input: (CAU3.INP)
  • Dòng đầu tiên ghi số nguyên dương n (1\le n\le 10^9)
  • Dòng tiếp theo ghi hai số nguyên dương l,r (1\le l\le r\le 10^9,r-l\le 1000)
Output: (CAU3.OUT)
  • Dòng thứ nhất ghi số nguyên dương k là số lượng các số m không tương đồng với n trong đoạn [l,r]
  • Dòng thứ hai ghi k số nguyên dương, các số ghi cách nhau dấu cách, là các số không tương đồng với n tìm được ghi theo thứ tự tăng dần
Subtasks
  • Subtask 1 (35\%): n\le 100,1\le l\le r\le 100
  • Subtask 2 (65\%): Không có ràng buộc gì thêm

Sample

Input (CAU3.INP)
6
8 12
Output (CAU3.OUT)
4
8 9 10 11

Bình luận đầu tiên

Bình luận

Không có bình luận nào.