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

[Sang_Ngo_Quoc]

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ố.

[noname00 (HK boy)]

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.

[SITUVN.gcd]

hiệu của tổng 2 tập là n

E hèm, là m chứ!

[noname00 (HK boy)]

Hì, gõ nhầm

[Wallace_Wu]

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

[Sang_Ngo_Quoc]

hí mình hk ptit mừ ^^