10.04.2017

Phân tích về số 0

Chọn HSG lớp 12 vòng 2 ngày thứ 1, Long An 2013, Bài 3/3
Mỗi một số nguyên dương đều có thể biểu diễn dưới dạng tích của hai số nguyên dương X, Y sao cho X<=Y. Nếu như trong cách phân tích này ta thay X bởi X-1 còn Y bởi Y+1 thì sau khi tính tích của chúng, ta thu được hoặc là một số nguyên dương mới, hoặc là số 0.
Nếu như kết quả là khác 0 thì ta lặp lại thủ tục này đối với số thu được. Rõ ràng là nếu áp dụng liên tiếp thủ tục trên, cuối cùng ta sẽ đến được số 0.
Ví dụ: số 6 có hai cách phân tích là 1*6, 2*3. Cách phân tích thứ nhất cho ta tích mới là 0=(1-1)*(6+1), cách phân tích thứ hai cho ta tích mới là 4 =(2-1)*(3+1), tiếp tục phân tích số 4 có hai cách phân tích là 1*4, 2*2. Cách phân tích thứ nhất cho ta tích mới là 0=(1-1)*(4+1), cách phân tích thứ hai cho ta tích mới là  3=(2-1)*(2+1). Số 3 có một cách phân tích là 1*3 cho ta tích mới là 0=(1-1)*(3+1).
Yêu cầu: Cho trước số nguyên dương N (1<=N<=10000), hãy đưa ra tất cả các số nguyên dương khác nhau có thể gặp trong việc áp dụng thủ tục đã mô tả đối với N.
Dữ liệu: Vào từ file văn bản KHONG.INP chứa số nguyên dương N
Kết quả: Ghi ra file văn bản KHONG.OUT:
 - dòng đầu tiên ghi K là số lượng số thu được
 - Trong các dòng tiếp theo lần lượt ghi K số thu được theo thứ tự tăng dần bắt đầu từ 0, mỗi dòng ghi 5 số cách nhau ít nhất một dấu trắng, trừ dòng cuối cùng có thể ít hơn 5 số.
Ví dụ:
   KHONG.INP
      6
   KHONG.OUT
      3
      0 3 4
   KHONG.INP
      12
   KHONG.OUT
      6
      0 3 4 6 7
      10

                                                           Lời giải tham khảo

No comments:

Post a Comment

Cảm ơn bạn đã nhận xét