Chia số từ 1 đến n thành 2 tập sao cho chênh lệch của tổng 2 tập là m và tổng các phần tử của 2 tập là các số nguyên tố cùng nhau

mn giúp mình bài này vs ạ mình chưa có ý tưởng luôn á :((

Cho hai số tự nhiên n, m. Nhiệm vụ của bạn là xác định xem có thể chia các số từ 1 đến n thành hai tập sao cho giá trị tuyệt đối của hiệu tổng hai tập là m và tổng các phần tử của cả hai tập là các số đồng nguyên tố (co-prime : nguyên tố cùng nhau) hay không?

Ví dụ

  • n =5, m = 7 ta có kết quả là Yes vì ta chia thành 2 tập {1, 2, 3, 5} và 4 có giá trị tuyệt đối của tổng hai tập là 7 và là các số nguyên tố cùng nhau.

  • Với n=6, m=3 ta có câu trả lời là No vì ta có thể tìm ra hai tập {1, 2, 4, 5} và {3, 6} có trị tuyệt đối của tổng là 3 tuy nhiên cặp 12=1+2+4+5 và 9=3 + 6 không là đồng nguyên tố.

Lạ nhỉ.

Các số từ 1 -> n có tổng là (n * (n + 1)) / 2. Biết tổng 2 tập là (n * (n + 1)) / 2, hiệu của tổng 2 tập là m, giải ra tổng mỗi tập. Xem 2 số tìm được này có nguyên tố cùng nhau hay không thôi.

  • Nếu 2 số tìm được không phải là số nguyên hoặc không nguyên tố cùng nhau -> No.
  • Nếu 2 số tìm được nguyên tố cùng nhau -> xem có thể biểu diễn được thành tổng 1 số số nào đó trong khoảng [1, n] hay không, nếu có thì Yes, nếu không thì No.
6 Likes

E hèm, là m chứ!

3 Likes

Hì, gõ nhầm :sweat_smile:

3 Likes

Này có mùi PTIT :)))))

2 Likes

hí mình hk ptit mừ ^^

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?